POJ 1106 Transmitters(计算几何)

切计算几何，感觉计算几何的算法还不熟。此题，枚举线段和圆点的直线，平分一个圆

 1 #include <iostream>
 2 #include <cstring>
 3 #include <cstdio>
 4 #include <cstdlib>
 5 #include <cmath>
 6 using namespace std;
 7 #define eps 1e-8
 8 struct point
 9 {
10     double x,y;
11 }p[201];
12 double dis(point p1,point p2)
13 {
14     return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));
15 }
16 double xmult(point p1,point p2,point p0)
17 {
18     return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
19 }
20 int main()
21 {
22     point r;
23     double d;
24     int n,m,i,j,ans,temp;
25     while(scanf("%lf%lf%lf",&r.x,&r.y,&d)!=EOF)
26     {
27         if(d < 0) break;
28         scanf("%d",&n);
29         m = 0;
30         for(i = 0;i < n;i ++)
31         {
32             scanf("%lf%lf",&p[i].x,&p[i].y);
33         }
34         for(i = 0;i < n;i ++)
35         {
36             if(dis(p[i],r) > d)
37             continue;
38             p[m++] = p[i];
39         }
40         ans = 0;
41         for(i = 0;i < m;i ++)
42         {
43             temp = 0;
44             for(j = 0;j < m;j ++)
45             {
46                 if(xmult(p[i],p[j],r) >= 0)
47                 temp ++;
48             }
49             ans = max(ans,temp);
50         }
51         printf("%d
",ans);
52     }
53     return 0;
54 }

。