POJ1106(简单几何--极角排序)

题目：Transmitters

题意：给一个半圆的半径和圆心坐标，再给平面上的n个点，这个半圆可以绕圆心任意旋转，问半圆最多能覆盖多少个点？

分析：本题可以这样做，我们只需要考虑到圆心距离小于或者等于半径的那些点，因为大于半径的点一定不能覆盖到，那么这

样我们把符合条件的点全部存入一个数组p[]，那么然后就二重循环枚举每一个点与圆心所连的直线的的左侧有多少个点，记录

最大即可。

#include <iostream>
#include <string.h>
#include <algorithm>
#include <stdio.h>
#include <math.h>

using namespace std;

const int N=50000;
const double eps=1e-9;

struct Point
{
    double x,y;
};

Point p[N];

double cross(Point A,Point B,Point C)
{
    return (B.x-A.x)*(C.y-A.y)-(B.y-A.y)*(C.x-A.x);
}

double dist(Point A,Point B)
{
    return (A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y);
}

int main()
{
    int k,n;
    Point t,cir;
    double d,r;
    while(cin>>cir.x>>cir.y>>r)
    {
        k=0;
        if(r<0) break;
        cin>>n;
        for(int i=0;i<n;i++)
        {
            cin>>t.x>>t.y;
            d=dist(t,cir);
            if(d<r*r||fabs(d-r*r)<eps) //表示点在圆内或者在圆上
            {
                p[k].x=t.x;
                p[k].y=t.y;
                k++;
            }
        }
        int maxval=0;
        for(int i=0;i<k;i++)
        {
            int count=1;
            for(int j=0;j<k;j++)
            {
                if(i!=j&&cross(cir,p[i],p[j])>=0)
                    count++;
            }
            if(count>maxval) maxval=count;
        }
        cout<<maxval<<endl;
    }
    return 0;
}

最后

以上就是刻苦乌冬面为你收集整理的POJ1106(简单几何--极角排序)的全部内容，希望文章能够帮你解决POJ1106(简单几何--极角排序)所遇到的程序开发问题。

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