wujiawei@HIT

ACM -- Fighting

常用链接

统计

最新评论

单位圆覆盖平面上点

HOJ 2704 Phone Cell

题目大意:给定圆的半径,以及平面上的一些点的坐标,问用此半径的圆最多可覆盖平面上多少点

我的做法:首先枚举一个圆与其他圆的相交情况,记录两圆相交的弧,也就是记录两个交点对于圆心的极角,并且作上标记,进入的点为+1,退出的点为-1。那么对于每个圆可以得到若干个极角的区间,所以排序之后再扫描一遍,遇到进入的点计数器+1,遇到退出的计数器-1,每次都动态更新最大值就可以了。在其中要注意当两点极角跨越0极角的时候会出现问题,所以可以将所有的极角都扩大到[0, 4π)上,即所有的极角都加2π然后进行统计即可。

Code:

 

  1#include <iostream>
  2
  3#include <cmath>
  4
  5#define N 8096
  6
  7#define M 2024
  8
  9using namespace std;
 10
 11int n;
 12
 13double R;
 14
 15const double pi( acos(-1.0));
 16
 17struct point
 18
 19{
 20
 21    int x, y;
 22
 23}
p[M];
 24
 25struct seg
 26
 27{
 28
 29    double apha;
 30
 31    int flag;
 32
 33}
s[N];
 34
 35bool cmp(seg a, seg b)
 36
 37{
 38
 39    return a.apha < b.apha;
 40
 41}

 42
 43int main()
 44
 45{
 46
 47    while (scanf("%d %lf"&n, &R) == 2 )
 48
 49    {
 50
 51        if(n == 0 && R == 0break;
 52
 53        for (int i(0); i < n; i++)
 54
 55            scanf("%d %d"&p[i].x, &p[i].y);
 56
 57        R = R + 0.001;
 58
 59        int cnt = 0;
 60
 61        int ans = 0, sum = 0;
 62
 63        point tp;
 64
 65        double dist, a1, a2;
 66
 67        for (int i(0); i < n; i++)
 68
 69        {
 70
 71            cnt = 0;
 72
 73            for (int j(0); j < n; j++)
 74
 75            {
 76
 77                if (i == j)
 78
 79                    continue;
 80
 81                tp.x = p[i].x - p[j].x;
 82
 83                tp.y = p[i].y - p[j].y;
 84
 85                dist = sqrt(tp.x * tp.x + tp.y * tp.y);
 86
 87 
 88
 89                if(dist <= 2 * R)
 90
 91                {
 92
 93                    double ang = atan2(p[j].y - p[i].y, p[j].x - p[i].x);
 94
 95                    if(ang < 0) ang += 2 * pi;
 96
 97                    double tpa = acos(dist / (2 * R));
 98
 99                    a1 = ang + tpa + 2 * pi;
100
101                    a2 = ang - tpa + 2 * pi;
102
103                    s[cnt].apha = a2, s[cnt].flag = 1;
104
105                    cnt++;
106
107                    s[cnt].apha = a1, s[cnt].flag = 0;
108
109                    cnt++;
110
111                }

112
113            }

114
115            if (ans >= cnt / 2)
116
117                continue;
118
119            sort(s, s + cnt, cmp);
120
121            sum = 0;
122
123            for (int j(0); j < cnt; j++)
124
125            {
126
127                if (s[j].flag) sum ++;
128
129                else sum --;
130
131                if(sum > ans) ans = sum;
132
133            }

134
135        }

136
137        printf("It is possible to cover %d points.\n", ans + 1);
138
139    }

140
141    return 0;
142
143}

144
145


HOJ 1799 Circle and points 做法同上题一样

  1#include <iostream>
  2
  3#include <cmath>
  4
  5#include <algorithm>
  6
  7#define N 8096
  8
  9#define M 2024
 10
 11using namespace std;
 12
 13int n;
 14
 15double R;
 16
 17const double pi( acos(-1.0));
 18
 19struct point
 20
 21{
 22
 23    double x, y;
 24
 25}
p[M];
 26
 27struct seg
 28
 29{
 30
 31    double apha;
 32
 33    int flag;
 34
 35}
s[N];
 36
 37bool cmp(seg a, seg b)
 38
 39{
 40
 41    return a.apha < b.apha;
 42
 43}

 44
 45int main()
 46
 47{
 48
 49    while (scanf("%d"&n) == 1 )
 50
 51    {
 52
 53        R = 1;
 54
 55        if(n == 0 ) break;
 56
 57        for (int i(0); i < n; i++)
 58
 59            scanf("%lf %lf"&p[i].x, &p[i].y);
 60
 61        int cnt = 0;
 62
 63        int ans = 0, sum = 0;
 64
 65        point tp;
 66
 67        double dist, a1, a2;
 68
 69        for (int i(0); i < n; i++)
 70
 71        {
 72
 73            cnt = 0;
 74
 75            for (int j(0); j < n; j++)
 76
 77            {
 78
 79                if (i == j)
 80
 81                    continue;
 82
 83                tp.x = p[i].x - p[j].x;
 84
 85                tp.y = p[i].y - p[j].y;
 86
 87                dist = sqrt(tp.x * tp.x + tp.y * tp.y);
 88
 89 
 90
 91                if(dist <= 2 * R)
 92
 93                {
 94
 95                    double ang = atan2(p[j].y - p[i].y, p[j].x - p[i].x);
 96
 97                    if(ang < 0) ang += 2 * pi;
 98
 99                    double tpa = acos(dist / (2 * R));
100
101                    a1 = ang + tpa + 2 * pi;
102
103                    a2 = ang - tpa + 2 * pi;
104
105                    s[cnt].apha = a2, s[cnt].flag = 1;
106
107                    cnt++;
108
109                    s[cnt].apha = a1, s[cnt].flag = 0;
110
111                    cnt++;
112
113                }

114
115            }

116
117            if (ans >= cnt / 2)
118
119                continue;
120
121            sort(s, s + cnt, cmp);
122
123            sum = 0;
124
125            for (int j(0); j < cnt; j++)
126
127            {
128
129                if (s[j].flag) sum ++;
130
131                else sum --;
132
133                if(sum > ans) ans = sum;
134
135            }

136
137        }

138
139        printf("%d\n", ans + 1);
140
141    }

142
143    return 0;
144
145}

146
147

HOJ 2940 Pit Lord 加上了每点的权值,做法类似

posted on 2010-08-21 14:17 wujiawei 阅读(924) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理