POJ 1981 Circle and Points （扫描线）

【题目链接】 http://poj.org/problem?id=1981

 

【题目大意】

　　给出平面上一些点，问一个半径为1的圆最多可以覆盖几个点

 

【题解】

　　我们对于每个点画半径为1的圆，那么在两圆交弧上的点所画的圆，一定可以覆盖这两个点
　　我们对于每个点计算出其和其它点的交弧，对这些交弧计算起末位置对于圆心的极角，
　　对这些我们进行扫描线操作，统计最大交集数量就是答案。

 

【代码】

#include <cstdio>
#include <algorithm>
#include <cmath> 
#include <cstring>
using namespace std;
double EPS=1e-10;
double add(double a,double b){
    if(abs(a+b)<EPS*(abs(a)+abs(b)))return 0;
    return a+b;
}
const int MAX_N=310;
struct P{
    double x,y;
    P(){}
    P(double x,double y):x(x),y(y){}
    P operator + (P p){return P(add(x,p.x),add(y,p.y));}
    P operator - (P p){return P(add(x,-p.x),add(y,-p.y));}
    P operator * (double d){return P(x*d,y*d);}
    double dot(P p){return add(x*p.x,y*p.y);} //点积
    double det(P p){return add(x*p.y,-y*p.x);}  //叉积
}ps[MAX_N];
double dist(P p,P q){return sqrt((p-q).dot(p-q));}
struct PolarAngle{
    double angle;
    bool flag;
}as[MAX_N];
bool cmp_a(PolarAngle a,PolarAngle b){
	return a.angle<b.angle;
}
int solve(int n,double r){
    int ans=1;
    for(int i=0;i<n;i++){
        int m=0; double d;
        for(int j=0;j<n;j++){
            if(i!=j&&(d=dist(ps[i],ps[j]))<=2*r){
                double phi=acos(d/2);
                double theta=atan2(ps[j].y-ps[i].y,ps[j].x-ps[i].x);
                as[m].angle=theta-phi,as[m++].flag=1;
                as[m].angle=theta+phi,as[m++].flag=0;
            }
        }sort(as,as+m,cmp_a);
        for(int sum=1,j=0;j<m;j++){
            if(as[j].flag)sum++;
            else sum--;
            ans=max(ans,sum);
        }
    }return ans;
}
int N;
int main(){
    while(scanf("%d",&N),N){
        for(int i=0;i<N;i++)scanf("%lf%lf",&ps[i].x,&ps[i].y);
        printf("%d\n",solve(N,1.0));
    }return 0;
}