【解题报告】POJ-1106 Transmitters

原题地址:http://poj.org/problem?id=1106

题目大意:

给定一些平面的点以及一个圆心和半径,过圆心作一个半圆,求点在半圆中点最多多少个。

解题思路:

首先将给定点中和圆心的距离超过半径的点排除,然后遍历每个点,作点和圆心的连线,求出一边的点的个数,取最大值就是答案。

代码:

【解题报告】POJ-1106 Transmitters
 1 #include<stdio.h>
 2 #include<iostream>
 3 #include<cmath>
 4 using namespace std;
 5 class point
 6 {
 7 public:
 8     double x,y;
 9     point(int xx=0,int yy=0){x=xx;y=yy;}
10     point(point& p){x=p.x;y=p.y;}
11     point operator-(const point&);//向量减法
12     double operator*(const point& p){return x*p.y-y*p.x;}//向量叉乘
13 };
14 point point::operator-(const point& p)
15 {
16     point p1(x-p.x , y-p.y);
17     return p1;
18 }
19 double Distance(point& p1,point& p2)
20 {
21     return sqrt(pow((p2.y-p1.y),2)+pow((p2.x-p1.x),2));
22 }
23 int main()
24 {
25     point po,p[1005];
26     int t,s,maxs,i,j;
27     double r;
28     while(cin>>po.x>>po.y>>r)
29     {
30         if(r<0) return 0;
31         cin>>t;
32         for(i=0;i<t;)//排除距离超过半径的点
33         {
34             cin>>p[i].x>>p[i].y;
35             if(Distance(p[i],po)<=r) {i++;}
36             else {t--;}
37         }
38         maxs=0;
39         for(i=0;i<t;i++)
40         {
41             s=0;
42             for(j=0;j<t;j++)
43             {
44                 if((po-p[j])*(p[i]-p[j])>=0) {s++;}//向量的叉乘大于零即在直线的一边
45             }
46             if(s>maxs) maxs=s;
47         }
48         printf("%d\n",maxs);
49     }
50     return 0;
51 }
View Code

【解题报告】POJ-1106 Transmitters

上一篇:typeof instanceof


下一篇:POJ 1470 Closest Common Ancestors (最近公共祖先LCA 的离线算法Tarjan)