poj1981 Circle and Points 单位圆覆盖问题

  1 /**
  2  * code generated by JHelper
  3  * More info: https://github.com/AlexeyDmitriev/JHelper
  4  * @author xyiyy @https://github.com/xyiyy
  5  */
  6 
  7 #include <iostream>
  8 #include <fstream>
  9 
 10 //#####################
 11 //Author:fraud
 12 //Blog: http://www.cnblogs.com/fraud/
 13 //#####################
 14 //#pragma comment(linker, "/STACK:102400000,102400000")
 15 #include <iostream>
 16 #include <sstream>
 17 #include <ios>
 18 #include <iomanip>
 19 #include <functional>
 20 #include <algorithm>
 21 #include <vector>
 22 #include <string>
 23 #include <list>
 24 #include <queue>
 25 #include <deque>
 26 #include <stack>
 27 #include <set>
 28 #include <map>
 29 #include <cstdio>
 30 #include <cstdlib>
 31 #include <cmath>
 32 #include <cstring>
 33 #include <climits>
 34 #include <cctype>
 35 
 36 using namespace std;
 37 #define mp(X, Y) make_pair(X,Y)
 38 #define rep(X, N) for(int X=0;X<N;X++)
 39 
 40 //
 41 // Created by xyiyy on 2015/8/10.
 42 //
 43 
 44 #ifndef JHELPER_EXAMPLE_PROJECT_P_HPP
 45 #define JHELPER_EXAMPLE_PROJECT_P_HPP
 46 
 47 const double EPS = 1e-9;
 48 
 49 double add(double a, double b) {
 50     if (fabs(a + b) < EPS * (fabs(a) + fabs(b)))return 0;
 51     return a + b;
 52 }
 53 
 54 class P {
 55 public:
 56     double x, y;
 57 
 58     P() { }
 59 
 60     P(double x, double y) : x(x), y(y) { }
 61 
 62     P  operator+(const P &p) {
 63         return P(add(x, p.x), add(y, p.y));
 64     }
 65 
 66     P operator-(const P &p) {
 67         return P(add(x, -p.x), add(y, -p.y));
 68     }
 69 
 70     P operator*(const double &d) {
 71         return P(x * d, y * d);
 72     }
 73 
 74     P operator/(const double &d) {
 75         return P(x / d, y / d);
 76     }
 77 
 78     double dot(P p) {
 79         return add(x * p.x, y * p.y);
 80     }
 81 
 82 
 83     double abs() {
 84         return sqrt(abs2());
 85     }
 86 
 87     double abs2() {
 88         return dot(*this);
 89     }
 90 
 91 };
 92 
 93 
 94 
 95 //直线和直线的交点
 96 /*P isLL(P p1,P p2,P q1,P q2){
 97     double d = (q2 - q1).det(p2 - p1);
 98     if(sig(d)==0)return NULL;
 99     return intersection(p1,p2,q1,q2);
100 }*/
101 
102 
103 //四点共圆判定
104 /*bool onC(P p1,P p2,P p3,P p4){
105     P c = CCenter(p1,p2,p3);
106     if(c == NULL) return false;
107     return add((c - p1).abs2(), -(c - p4).abs2()) == 0;
108 }*/
109 
110 //三点共圆的圆心
111 
112 
113 #endif //JHELPER_EXAMPLE_PROJECT_P_HPP
114 
115 const int MAXN = 710;
116 P ps[MAXN];
117 pair<double, bool> arc[MAXN];
118 
119 class poj1981 {
120 public:
121     void solve(std::istream &in, std::ostream &out) {
122         int n;
123         P t;
124         while (in >> n && n) {
125             rep(i, n)in >> ps[i].x >> ps[i].y;
126             int ans = 1;
127             rep(i, n) {
128                 int num = 0;
129                 rep(j, n) {
130                     if (i == j)continue;
131                     double d;
132                     if ((d = (ps[i] - ps[j]).abs()) <= 2) {
133                         double a = acos(d / 2);
134                         double b = atan2((ps[j].y - ps[i].y), (ps[j].x - ps[i].x));
135                         arc[num++] = mp(b - a, 1);
136                         arc[num++] = mp(b + a, 0);
137                     }
138                 }
139                 sort(arc, arc + num);
140                 int res = 1;
141                 rep(j, num) {
142                     if (arc[j].second)res++;
143                     else res--;
144                     ans = max(ans, res);
145                 }
146             }
147             out << ans << endl;
148         }
149     }
150 };
151 
152 int main() {
153     std::ios::sync_with_stdio(false);
154     std::cin.tie(0);
155     poj1981 solver;
156     std::istream &in(std::cin);
157     std::ostream &out(std::cout);
158     solver.solve(in, out);
159     return 0;
160 }