poj pku 1981 Circle and Points 点与圆 位置关系
[*]题目描述: 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, 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) > 2.0)continue;count = 0;cent = circle(dot, dot);for(k = 0; k < n; k++) {if(dot_on_in_circle(dot, cent, 1.0))count++;}if(count > max)max = count;}}printf("%d\n", max);}return 0;}
页:
[1]