http://acm.pku.edu.cn/JudgeOnline/problem?id=1106
Код:
#include<stdio.h> #include<math.h> #define MAXN 151 #define pi 3.1415926 class POINT { public: double x,y; }; POINT e[MAXN]; int n; POINT o; double r; bool check[MAXN]; double dist(POINT p1) { return(sqrt(double((p1.x-o.x)*(p1.x-o.x)+(p1.y-o.y)*(p1.y-o.y)))); } double angle(POINT s,POINT e) { double cosfi,fi,norm; double dsx = s.x - o.x; double dsy = s.y - o.y; double dex = e.x - o.x; double dey = e.y - o.y; cosfi=dsx*dex+dsy*dey; norm=(dsx*dsx+dsy*dsy)*(dex*dex+dey*dey); cosfi /= sqrt( norm ); if (cosfi >= 1.0 ) return 0; else if (cosfi <= -1.0 ) return 0; fi=acos(cosfi); if (dsx*dey-dsy*dex>0) return fi; return -fi; } int solve() { int i,j,count1,key=0; double temp,dis; for(i=1;i<=n;i++) { dis = dist(e[i]); if(dis<=r) check[i] = 1; else check[i] = 0; } for(i=1;i<=n;i++) { if(check[i]) { count1=1; for(j=1;j<=n;j++) { if(i!=j && check[j]) { temp = angle(e[i],e[j]); if(temp>=0.0) count1++; } } if(count1>key) key = count1; } } return key; } int main() { int i; scanf("%lf %lf %lf",&o.x,&o.y,&r); while(r>0.0) { scanf("%d",&n); for(i=1;i<=n;i++) scanf("%lf %lf",&e[i].x,&e[i].y); for(i=0;i<MAXN;i++) check[i] = 0; printf("%d\n",solve()); scanf("%lf %lf %lf",&o.x,&o.y,&r); } return 0; }