poj 1106 Transmitters (枚举+叉积运用)

题目链接：http://poj.org/problem?id=1106

算法思路：由于圆心和半径都确定，又是180度，这里枚举过一点的直径，求出这个直径的一个在圆上的端点，就可以用叉积的大于，等于，小于0判断点在直径上，左，右。 这里要记录直径两边的加直径上的点的个数，去最大的。

代码：

#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;

const double eps = 1e-8;
const double PI = acos(-1.0);
const double INF = 1000000000000000.000;

struct Point{
    double x,y;
    Point(double x=0, double y=0) : x(x),y(y){ }    //构造函数
};
typedef Point Vector;

struct Circle{
     Point c;
     double r;
     Circle() {}
     Circle(Point c,double r): c(c),r(r) {}
};
Vector operator + (Vector A , Vector B){return Vector(A.x+B.x,A.y+B.y);}
Vector operator - (Vector A , Vector B){return Vector(A.x-B.x,A.y-B.y);}
Vector operator * (double p,Vector A){return Vector(A.x*p,A.y*p);}
Vector operator / (Vector A , double p){return Vector(A.x/p,A.y/p);}

bool operator < (const Point& a,const Point& b){
    return a.x < b.x ||( a.x == b.x && a.y < b.y);
}

int dcmp(double x){
    if(fabs(x) < eps) return 0;
    else              return x < 0 ? -1 : 1;
}
bool operator == (const Point& a, const Point& b){
    return dcmp(a.x - b.x) == 0 && dcmp(a.y - b.y) == 0;
}

///向量（x,y）的极角用atan2(y,x);
inline double Dot(Vector A, Vector B){ return A.x*B.x + A.y*B.y; }
inline double Length(Vector A)    { return sqrt(Dot(A,A)); }
inline double Angle(Vector A, Vector B)  { return acos(Dot(A,B) / Length(A) / Length(B)); }
double Cross(Vector A, Vector B)  { return A.x*B.y - A.y * B.x; }
Vector vecunit(Vector v){ return v / Length(v);} //单位向量

Point read_point(){
    Point A;
    scanf("%lf %lf",&A.x,&A.y);
    return A;
}


//多边形
//求面积
double PolygonArea(Point* p,int n){   //n个点
    double area = 0;
    for(int i=1;i<n-1;i++){
        area += Cross(p[i]-p[0],p[i+1]-p[0]);
    }
    return area/2;
}

/*************************************分 割 线*****************************************/

int main()
{
    //freopen("E:\acm\input.txt","r",stdin);

    Point O,P[155];
    double R;

    while(scanf("%lf %lf %lf",&O.x,&O.y,&R) == 3  && dcmp(R)>0)
    {
        int N;
        cin>>N;
        int cnt = 0;
        for(int i=1;i<=N;i++)
        {
            Point temp = read_point();
            double len = Length(temp-O);
            if(dcmp(len-R) > 0) continue;
            P[++cnt] = temp;
        }
        int ans = 0;
        for(int i=1; i<=cnt; i++)
        {
            if(P[i] == O)
            {
                ans = max(ans,1);
                continue;
            }
            int lnum = 1;
            int rnum = 1;
            Vector v = P[i] - O;
            v = (-1.0)*vecunit(v);
            Point T = O + R*v;
            for(int j=1; j<=cnt; j++)
            {
                if(i == j) continue;
                if(dcmp(Cross(P[j]-T,O-T)) > 0 )      lnum++;
                else if(dcmp(Cross(P[j]-T,O-T)) == 0) lnum++,rnum++;
                else                                  rnum++;
            }

            int num = max(lnum,rnum);
            ans = max(ans,num);
        }
        printf("%d
",ans);
    }
}