题目来源:
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; }