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

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

#include <iostream>
#include <cmath>
using namespace std;

#define eps 1e-6

struct 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.0
Point 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[i].x, &dot[i].y);
		
		for(i = 0; i < n; i++) {
			for(j = i + 1; j < n; j++) {
				if(dist(dot[i], dot[j]) > 2.0)
					continue;
				
				count = 0;
				cent = circle(dot[i], 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;
}