题目大意
给出平面上的一些点，求一个单位圆最多能够覆盖多少点。
思路
数据范围300，但是没有用，多组数据就是要卡的做法。 做法就是枚举每个点，做一个一这个点为圆心的单位圆。之后将所有在这个圆里的点弄出来，，以这些点为圆心做单位圆，与开始的单位圆会产生一段圆弧，最后求哪一段圆弧被覆盖的次数最多就是答案。
CODE
水过版
;struct Point{double x, y;Point(&__):x(_), y(__) {}Point() {}Point operator +(const Point &a)const {return Point(x + a.x, y + a.y);}Point operator -(const Point &a)const {return Point(x – a.x, y – a.y);}Point operator *(const double &a)const {return Point(x * a, y * a);}Point operator /(const double &a)const {return Point(x / a, y / a);}void Read() {scanf(“%lf%lf”, &x, &y);}}point[MAX];inline double Calc(const Point &p1, const Point &p2){return sqrt((p1.x – p2.x) * (p1.x – p2.x) + (p1.y – p2.y) * (p1.y – p2.y));}inline Point Change(const Point &v){return Point(-v.y, v.x);}int points;bool v[MAX];int stack[MAX], top;inline int GetAns(const Point &p1, const Point &p2){double dis = Calc(p1, p2) / 2;if(dis > 1.0) return 0;Point o = Point((p1.x + p2.x) / 2, (p1.y + p2.y) / 2) + (Change(p1 – p2) / (dis * 2)) * sqrt(1 – dis * dis);int re = 0;for(int i = 1; i <= top; ++i)re += Calc(point[stack[i]], o) <= 1.0 + EPS;return re + 1;}int main(){while(scanf(“%d”, &points), points) {for(int i = 1; i <= points; ++i)point[i].Read();int ans = 1;for(int i = 1; i <= points; ++i) {top = 0;for(int j = 1; j <= points; ++j)if(i != j && Calc(point[i], point[j]) < 2.0)stack[++top] = j;for(int j = 1; j <= top; ++j)ans = max(ans, GetAns(point[i], point[stack[j]]));}printf(“%d\n”, ans);}return 0;}
旁观者的姓名永远爬不到比赛的计分板上。
