下午莫名其妙的不开心, 刷一波题以后心情舒畅了许多... 明天就是我的handle日了, hanfei19910905...
题目描述:
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=41
给一个平面上的点集, 一个半圆的圆心与周长, 问按怎样的角度摆放半圆可以让半圆覆盖的点最多.
算法分析:
求出每个点"进入"和"退出"的时候的角度, 然后排序, 对环行区间进行统计.
注意应该先进入再退出...
zoj 1040
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<complex>
5 #include<algorithm>
6 #include<cmath>
7 using namespace std;
8 typedef complex<double> pnt;
9 const double pi = acos(-1.0);
10 const double eps = 1e-8;
11 inline double fix(double x){
12 while(x < 0) x+= pi*2;
13 while(x >= pi *2) x-=pi*2;
14 return x;
15 }
16 const int N = 160;
17 struct node{
18 double a;int c,id;
19 node(){}
20 node(double _a,int _c,int _id):a(_a),c(_c),id(_id){
21 }
22 bool operator < (const node &A) const{
23 return abs(a - A.a) <eps ? c < A.c : a < A.a;
24 }
25 } num[N];
26 int main(){
27 pnt O;
28 static pnt p[N];
29 int x,y,n; double r;
30 bool inner[N];
31 while(~scanf("%d%d%lf",&x,&y,&r) , r > 0) {
32 O = pnt(x,y);
33 cin >> n;
34 for(int i = 0; i < n; i++){
35 cin >> x >> y;
36 p[i] = pnt(x,y);
37 }
38 int len = 0;
39 for(int i =0; i < n; i++){
40 if(abs(p[i] - O) > r + eps) continue;
41 num[len++] = node(fix(arg(p[i] - O)), 0,i);
42 num[len++] = node(fix(arg(p[i] - O) + pi), 1,i);
43 }
44 sort(num, num+len);
45 memset(inner, 0 ,sizeof(inner));
46 int sum = 0, ans = 0;
47 for(int j = 0; j < 2*len; j++) {
48 int i = j % len, v = num[i].id;
49 if(num[i].c) {
50 if(inner[v]) sum --;
51 inner[v] = 0;
52 }
53 else {
54 sum += (inner[v] = 1);
55 }
56 if(sum > ans) ans = sum;
57 // cout<< v <<" "<< sum<<" "<<num[i].a << endl;
58 }
59 cout<< ans << endl;
60 }
61 }
62 posted on 2012-09-04 16:14
西月弦 阅读(260)
评论(2) 编辑 收藏 引用 所属分类:
解题报告