题目大意:给出平面内一些点,给一个圆心坐标和圆的半径,求在这个圆心的半圆最多能覆盖多少个点。
思路:暴力枚举就可以,数据量不是很大。先算出那些点有可能成为被覆盖的点,然后枚举所有的点与圆心连线成为圆的半径,用叉积验证是否在圆内即可。
CODE:
#include <cmath> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define MAX 1010 #define EPS 1e-4 using namespace std; struct Point{ double x,y; Point(double _x,double _y):x(_x),y(_y) {} Point() {} Point operator -(const Point &a) { return Point(x - a.x,y - a.y); } void Read() { scanf("%lf%lf",&x,&y); } }point[MAX],center; struct Line{ Point p1,p2; Line(Point _p1,Point _p2):p1(_p1),p2(_p2) {} Line() {} bool Judge(Point p) { Point a = p - p1,b = p - p2; return a.x * b.y - b.x * a.y <= 0; } }l; int points; bool in_range[MAX]; inline void Initialize(); inline double Calc(Point p1,Point p2); int main() { double x,y,r; while(scanf("%lf%lf",&x,&y) != EOF) { Initialize(); center = Point(x,y); scanf("%lf",&r); if(r < 0) continue; scanf("%d",&points); for(int i = 1;i <= points; ++i) { point[i].Read(); if(Calc(point[i],center) - r <= EPS) in_range[i] = true; } int ans = 0; for(int cnt,i = 1;i <= points; ++i) { l = Line(center,point[i]); cnt = 0; for(int j = 1;j <= points; ++j) if(in_range[j]) cnt += l.Judge(point[j]); ans = max(ans,cnt); } printf("%d\n",ans); } return 0; } inline double Calc(Point p1,Point p2) { return sqrt((p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y)); } inline void Initialize() { memset(in_range,false,sizeof(in_range)); }