poj pku 1981 Circle and Points 点与圆 位置关系

scott________

• 题目描述: http://poj.org/problem?id=1981
  
• 题目大意: 给定n 个点的坐标, 求单位圆最多可以覆盖(包括在圆上)多少个点.题目分析: 假设某单位圆能覆盖最多点, 可以右移该单位圆, 使得恰有两个点(或更多)在圆上.   所以思路是,枚举以任意两点,以及半径为1 所确定的圆(有两个,总是选圆心在右, 或在左的那个圆)即可.
  

#include <iostream>#include <cmath>using namespace std;#define eps 1e-6struct Point {double x, y;Point() {x = y = 0.00;}};//返回两点间距double dist(Point p1, Point p2) {return sqrt( (p1.x - p2.x) * (p1.x - p2.x) +(p1.y - p2.y) * (p1.y - p2.y) );}//判断点在圆内(包括圆上)bool dot_on_in_circle(Point p, Point c, double r) {  return (dist(p, c) < r + eps);}//返回p1, p2, 以及半径1, 所确定的圆的圆心(只是其中一个圆心)//保证dist(p1, p2) <= 2.0Point circle(Point p1, Point p2) {Point mid, ret;  mid.x = (p1.x + p2.x) / 2;  mid.y = (p1.y + p2.y) / 2;    double a = dist(p1, mid);  double d = sqrt(1.0 - a * a);    if(fabs(p1.x - p2.x) <= eps) {  ret.x = mid.x + d;  ret.y = mid.y;  return ret;  }    double alpha = atan((p1.y - p2.y) / (p1.x - p2.x));  //double alpha = atan(a / d);    ret.x = mid.x + d * sin(alpha);  ret.y = mid.y - d * cos(alpha);  return ret;}int main() {//freopen("in.txt", "r", stdin);int n, i, j, k, count, max;Point dot[305], cent;while(scanf("%d", &n) != EOF && n) {max = 1;for(i = 0; i < n; i++)scanf("%lf %lf", &dot.x, &dot.y);for(i = 0; i < n; i++) {for(j = i + 1; j < n; j++) {if(dist(dot, dot[j]) > 2.0)continue;count = 0;cent = circle(dot, dot[j]);for(k = 0; k < n; k++) {if(dot_on_in_circle(dot[k], cent, 1.0))count++;}if(count > max)max = count;}}printf("%d\n", max);}return 0;}