【解题报告】POJ-1106 Transmitters

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

题目大意:

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

解题思路:

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

代码:

 #include<stdio.h>
#include<iostream>
#include<cmath>
using namespace std;
class point
{
public:
double x,y;
point(int xx=,int yy=){x=xx;y=yy;}
point(point& p){x=p.x;y=p.y;}
point operator-(const point&);//向量减法
double operator*(const point& p){return x*p.y-y*p.x;}//向量叉乘
};
point point::operator-(const point& p)
{
point p1(x-p.x , y-p.y);
return p1;
}
double Distance(point& p1,point& p2)
{
return sqrt(pow((p2.y-p1.y),)+pow((p2.x-p1.x),));
}
int main()
{
point po,p[];
int t,s,maxs,i,j;
double r;
while(cin>>po.x>>po.y>>r)
{
if(r<) return ;
cin>>t;
for(i=;i<t;)//排除距离超过半径的点
{
cin>>p[i].x>>p[i].y;
if(Distance(p[i],po)<=r) {i++;}
else {t--;}
}
maxs=;
for(i=;i<t;i++)
{
s=;
for(j=;j<t;j++)
{
if((po-p[j])*(p[i]-p[j])>=) {s++;}//向量的叉乘大于零即在直线的一边
}
if(s>maxs) maxs=s;
}
printf("%d\n",maxs);
}
return ;
}
上一篇:好系统重装助手教你如何让win10系统快速开机


下一篇:Win7系统如何复制CMD命令提示符框中的内容