原题地址:http://poj.org/problem?id=1106
题目大意:
给定一些平面的点以及一个圆心和半径,过圆心作一个半圆,求点在半圆中点最多多少个。
解题思路:
首先将给定点中和圆心的距离超过半径的点排除,然后遍历每个点,作点和圆心的连线,求出一边的点的个数,取最大值就是答案。
代码:
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 }