zoj 1041 Transmitters 判断一个可以移动的半圆最多可容纳的点的个数

浏览数：26 / 时间：2015年06月11日

题目来源：

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=41

题意：判断一个可以移动的半圆最多可容纳的点的个数。

分析：计算在圆内的点，然后枚举这些点，将点和圆心的连线的直径的左右点统计，最大值即可。

代码如下：

const double EPS = 1e-12;
const int Max_N = 160;
double add(double a, double b){
    return (fabs(a + b) < EPS * ( fabs(a) + fabs(b) )) ? 0 : (a+ b) ;
}
struct Point{
    double x, y;
    Point(){}
    Point(double x , double y):x(x), y(y){}
    double dist(Point p){
        return sqrt( add( (x - p.x)*(x - p.x) , (y - p.y)*(y - p.y) ) ) ;
    }
    Point operator - (Point p){
        return Point( add(x ,- p.x) , add(y, - p.y)) ;
    }
    double operator ^(Point p){
        return add(x * p. y , - y * p.x) ;
    }
}po[Max_N];
Point ro ;
double r ;
int main(){
    int  n , i , j ,maxm ;
    while(scanf("%lf%lf%lf" , &ro.x , &ro.y , &r) && r > 0 ) {
        maxm = 0 ;
        scanf("%d" , &n) ;
        for(i = 0 ; i < n ; i++)
            scanf("%lf%lf" , &po[i].x ,&po[i].y ) ;
        int l = 0 ;
        for(i = 0 ; i< n ; i++)
            if( ro.dist(po[i]) - r <= EPS )
                po[l++] = po[i] ;
        n = l ;
        int left , right;
        for(i = 0 ; i < n ; i++){
            left = 0, right = 0;
            for(j = 0 ; j< n ; j++){
                    double d = (po[i] - ro)^(po[j] - ro) ;
                    if( d > 0) left ++ ;
                    else if( d < 0) right ++ ;
                    else{
                        left ++ ;
                        right ++ ;
                    }
            }
            maxm = maxm < left? left :maxm ;
            maxm = maxm < right ? right : maxm ;
        }
        printf("%d\n" , maxm ) ;
    }
    return 0;
}