POJ1106

Problem: Transmitters
Description: 给你一个半圆的圆心坐标和半径，再给你平面上的一些点，然后半圆绕圆心转动，问这个半圆最多可以覆盖多少个点。
Solution: 我们先预处理下，把到圆心距离大于半径的点去掉，然后枚举每个点，利用向量的叉积来判断剩余点是否在这个点与圆心所在直线的一边。最后维护一个最大值就可以了。
Code(C++):

#include <stdio.h>
#include <string.h>

#define MAX(a,b) ((a)>(b)? (a):(b))

typedef struct tagPoint{
    double x,y;
    tagPoint(){}
    tagPoint(int _x,int _y):
        x(_x),y(_y){}
}Point;

const int M=200;

double X,Y,R;

Point points[M];

double distan(Point tmp)
{
    return (tmp.x-X)*(tmp.x-X)+(tmp.y-Y)*(tmp.y-Y);
}

double vector_product(Point a,Point b)
{
    return a.x*b.y-a.y*b.x;
}

Point get_vector(Point a,Point b)
{
    Point tmp;
    tmp.x=b.x-a.x;
    tmp.y=b.y-a.y;
    return tmp;
}

int main()
{
    while(scanf("%lf%lf%lf",&X,&Y,&R),R>=0){

        int i,j;

        int tmp_top=0;
        scanf("%d",&tmp_top);
        for(i=0;i<tmp_top;i++)
            scanf("%lf%lf",&points[i].x,&points[i].y);
        int top=0;
        for(i=0;i<tmp_top;i++)
            if(R*R>=distan(points[i]))
                points[top++]=points[i];

        int ans=0;
        for(i=0;i<top;i++){
            int sum=0;
            for(j=0;j<top;j++)
                if(vector_product(get_vector(Point(X,Y),points[i]),
                    get_vector(Point(X,Y),points[j]))>=0)
                    ++sum;
            ans=MAX(ans,sum);
        }
        printf("%dn",ans);
    }
    return 0;
}

最后

以上就是悲凉大地为你收集整理的POJ1106的全部内容，希望文章能够帮你解决POJ1106所遇到的程序开发问题。

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