POJ 1106 Transmitters

题意：给定圆心和半径，和一些点，求半圆能覆盖的最大点数

思路：先去掉不在圆内的点，然后通过叉积判断是否在同侧

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const double eps=1e-11;
const double pi=acos(-1.0);
struct P
{
double x,y,R;
P(){}
P(double x,double y):x(x),y(y){
}
P operator +(P p){
return P(x+p.x,y+p.y);
}
P operator -(P p){
return P(x-p.x,y-p.y);
}
P operator /(double d){
return P(x/d,y/d);
}
double det(P p){
return x*p.y-y*p.x;
}
};
P p[1000000],r,q[1000000];
double dis(P a,P b)
{
double c=(a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
return sqrt(c);
}
int ln;
int n;
int main()
{
while(~scanf("%lf%lf%lf",&r.x,&r.y,&r.R))
{
ln=0;
if(r.R<0)
break;
scanf("%d",&n);
for(int i=0;i<n;i++)
scanf("%lf%lf",&p[i].x,&p[i].y);
for(int i=0;i<n;i++)
{
if(dis(p[i],r)<=r.R)
{
q[ln++]=p[i];
}
}
int ans=0;
for(int i=0;i<ln;i++)
{
int a=0;
int j=i;
for(int j=0;j<ln;j++)
{
if((q[i]-r).det(q[j]-r)>=0)
a++;
}
ans=max(ans,a);
}
printf("%dn",ans);
}
return 0;
}

最后

以上就是风趣学姐为你收集整理的POJ 1106 Transmitters的全部内容，希望文章能够帮你解决POJ 1106 Transmitters所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。