题目:
POJ 1981 Circle and Points
HDU 1077 Catching Fish
题意:
给出n个点的二维点坐标,问单位圆最多能覆盖多少点?
分析:
①:
最优的情况一定是有两个点在圆弧上。先枚举两个点,计算两点在圆弧上的单位圆(一般会有两个)
但是可以统一取一个方向的(也就是AB取一个然后BA取另外一个).然后枚举所有点,计算在这个单位圆内的点的个数。
这样做的时间复杂度是O(n^3).
②:
对每个点以R为半径画圆,对N个圆两两求交。这一步O(N^2)。问题转化为求被覆盖次数最多的弧。
因为如果最优圆覆盖A点那么最优圆一定在以A点为圆心的圆弧上。那么圆弧倍覆盖多少次也就意味着
以这条圆弧为上任意一点为圆心花园能覆盖多少点。
对每一个圆,求其上的每段弧重叠次数。假如A圆与B圆相交。A上[PI/3, PI/2]的区间被B覆盖(PI为圆周率)。
那么对于A圆,我们在PI/3处做一个+1标记,在PI/2处做一个-1标记。
对于[PI*5/3, PI*7/3]这样横跨0点的区间只要在0点处拆成两段即可。
将一个圆上的所有标记排序,从头开始扫描。初始total=0,碰到+1标记给total++,碰到-1标记total–。
扫描过程中total的最大值就是圆上被覆盖最多的弧。求所有圆的total的最大值就是答案。
极角排序需要2*n*logn,总复杂度O(N^2 * logN)
//1264K 1357MS
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <climits>
#include <cmath>
using namespace std;
const int MAX_N=310;
const double eps=1e-6;
const double R=1.0;//定义覆盖圆半径为Rint T,n;struct Point{