POJ 1106 - Transmitters

http://poj.org/problem?id=1106

概要

N 個の点が与えられる． 与えられた中心座標と半径をもつ半円を考えて，半円に含まれる点の数を最大化する問題．

制約

• 1 <= N <= 150
• 座標 (x, y) は整数で 0 <= x, y <= 1000
• 座標が重複している点は無い
• 半径 r は浮動小数で r > 0.0

解法

まず平行移動させて円の中心が原点にくるようにする． 原点からの距離が r より大きい点は最初から除外して考えない．

あとは各点について，その点と原点を底辺(?)とする半円を考えて，その半円に含まれている点を数えて最大値をとればいい．

 1 #include <cstdio>
 2 #include <vector>
 3 #include <complex>
 4 #include <cmath>
 5 #include <algorithm>
 6 using namespace std;
 7 typedef complex<double> P;
 8 static const double PI = acos(-1.0);
 9 static const double EPS = 1e-6;
10 
11 int main()
12 {
13   double x, y, r;
14   while (scanf("%lf %lf %lf", &x, &y, &r) != EOF && r > 0.0) {
15     const P center(x, y);
16     int N;
17     scanf("%d", &N);
18     vector<P> v;
19     for (int i = 0; i < N; i++) {
20       scanf("%lf %lf", &x, &y);
21       P p(x, y);
22       p -= center;
23       //if (abs(p) <= r) {
24       if (abs(p) - r <= EPS) {
25         v.push_back(p);
26       }
27     }
28     N = v.size();
29 
30     int ans = 0;
31     for (int i = 0; i < N; i++) {
32       int c = 0;
33       for (int j = 0; j < N; j++) {
34         //if (fmod(2*PI + arg(v[(i+j)%N]) - arg(v[i]), 2*PI) <= PI) {
35         if (fmod(2*PI + arg(v[(i+j)%N]) - arg(v[i]), 2*PI) - PI <= EPS) {
36           ++c;
37         }
38       }
39       ans = max(ans, c);
40     }
41     printf("%d\n", ans);
42   }
43   return 0;
44 }