栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 面试经验 > 面试问答

zoj 3575 Under Attack III

面试问答 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

zoj 3575 Under Attack III

#include<cstdio>#include<cmath>#include<algorithm>const double EPSILON = 1e-15;int signum(double x) { return x < -EPSILON? -1: x > EPSILON;}struct Point { double x, y; Point(double x = 0.0, double y = 0.0): x(x), y(y) {} Point &operator +=(const Point &o) { return x += o.x, y += o.y, *this; } Point &operator -=(const Point &o) { return x -= o.x, y -= o.y, *this; } Point &operator *=(double k) { return x *= k, y *= k, *this; } Point &operator /=(double k) { return x /= k, y /= k, *this; } Point rotate() const { return Point(-y, x); } double norm2() const; double norm() const; Point normalize() const; double arg() const { return atan2(y, x); }};Point operator ==(const Point &a, const Point &b) { return signum(a.x - b.x) == 0 && signum(a.y - b.y) == 0;}Point operator +(Point a, const Point &b) { return a += b;}Point operator -(Point a, const Point &b) { return a -= b;}Point operator *(Point a, double k) { return a *= k;}Point operator *(double k, Point a) { return a *= k;}Point operator /(Point a, double k) { return a /= k;}double det(const Point &a, const Point &b) { return a.x * b.y - b.x * a.y;}double dot(const Point &a, const Point &b) { return a.x * b.x + a.y * b.y;}double angle(const Point &a, const Point &b) { return atan2(det(a, b), dot(a, b));}double Point::norm2() const { return dot(*this, *this);}double Point::norm() const { return sqrt(norm2());}Point Point::normalize() const { return *this / norm();}const int N=200;Point p[N];double a,b,r;int n,maxCount;double distance(Point a,Point b) { return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));}void update(Point o) { int count=0; for(int i=0; i<n; ++i) { if(signum(r-distance(o,p[i]))>=0) { count++; } } maxCount=std::max(maxCount,count);}int main() { while(scanf("%lf%lf%d",&a,&b,&n)==3) { r=a; for(int i=0; i<n; ++i) { scanf("%lf%lf",&p[i].x,&p[i].y); p[i].y*=a/b; } maxCount=1; for(int i=0; i<n; ++i) { for(int j=i+1; j<n; ++j) { double d=distance(p[i],p[j]); if(signum(r-0.5*d)>=0) { Point mid=(p[i]+p[j])/2.0; Point unit=(p[i]-mid).rotate().normalize(); Point o=mid+unit*(sqrt(r*r-0.25*d*d)); update(o); unit=unit.rotate().rotate(); o=mid+unit*(sqrt(r*r-0.25*d*d)); update(o); } } } printf("%dn",maxCount); }}
转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/380131.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号