欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2022-03-02 10:41:12
...
[size=medium][list][*]题目描述: [url]http://poj.org/problem?id=1981[/url]
[*]题目大意: 给定n 个点的坐标, 求单位圆最多可以覆盖(包括在圆上)多少个点.
[*]题目分析: 假设某单位圆能覆盖最多点, 可以右移该单位圆, 使得恰有两个点(或更多)在圆上. 所以思路是,枚举以任意两点,以及半径为1 所确定的圆(有两个,总是选圆心在右, 或在左的那个圆)即可.[/list][/size]

#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;
}
相关标签: J# C C++ C#