ZOJ 1041 Transmitters

题意：给你一个能绕圆心转动的半径固定的半圆和N个点，问这个半圆最多能覆盖多少个点，半圆边界上的点也算在覆盖范围内。

首先把半圆半径之外的点全部排除，枚举剩余所有点与圆心的连线。判断在同一侧的点有多少个。

之前忽略的边界情况，WA一次。

View Code

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <cstdlib>
 4 #include <cmath>
 5 
 6 const int MAXN = 200;
 7 const double EPS = 1e-9;
 8 
 9 struct point
10 {
11     double x, y;
12 };
13 
14 point T;
15 point P[MAXN];
16 double R;
17 int N, cnt;
18 
19 int max( int a, int b )
20 {
21     return a > b ? a : b;
22 }
23 
24 double GetDis( point a, point b )
25 {
26     return sqrt( (a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y-b.y) );
27 }
28 
29 void GetLine( point a, point b, double& K, double &B )
30 {
31     K = ( a.y - b.y ) / ( a.x - b.x );
32     B = a.y - K*a.x;
33     return;
34 }
35 
36 void solved()
37 {
38     int ans = 0;
39     double K, B;
40     for ( int i = 0; i < cnt; ++i )
41     {
42         if ( fabs( P[i].x - T.x ) > EPS )
43         {
44             GetLine( T, P[i], K, B );
45             int count1 = 0;
46             int count0 = 0;
47             //printf( "K=%f B=%lf\n", K, B );
48             for ( int j = 0; j < cnt; ++j )
49             {
50                 //printf("y=%f\n", K * P[j].x - P[j].y + B );
51                 double temp = K * P[j].x - P[j].y + B;
52                 if ( temp > 0 ) ++count1;
53                 else if ( fabs( temp ) < EPS ) ++count0;
54             }
55             //printf("1=%d 0=%d\n", count1, count0 );
56             ans = max( ans, max( cnt - count1, count1 + count0 ) );
57         }
58         else
59         {
60             int count1 = 0;
61             int count0 = 0;
62             for ( int j = 0; j < cnt; ++j )
63             {
64                 if ( P[j].x - T.x > 0 ) ++count1;
65                 else if ( fabs( P[j].x - T.x ) < EPS ) ++count0;
66             }
67             //printf("**1=%d 0=%d\n", count1, count0 );
68             ans = max( ans, max( cnt - count1, count1 + count0 ) );
69         }
70     }
71 
72     printf("%d\n", ans );
73     return;
74 }
75 
76 int main()
77 {
78     while ( ~scanf( "%lf%lf%lf", &T.x, &T.y, &R ) )
79     {
80         if ( R < 0 ) break;
81         scanf( "%d", &N );
82         cnt = 0;
83         for ( int i = 0; i < N; ++i )
84         {
85             scanf( "%lf%lf", &P[cnt].x, &P[cnt].y );
86             double temp = GetDis( T, P[cnt] );
87             if ( temp < R || fabs( temp - R ) < EPS ) ++cnt;
88         }
89         //printf("cnt=%d\n", cnt);
90 
91         solved();
92     }
93     return 0;
94 }