放牧代码和思想
专注自然语言处理、机器学习算法

POJ 1981 Circle and Points 题解 《挑战程序设计竞赛》

目录

POJ 1981 Circle and Points

套圈:平面上有N个点,用单位圆去套,最多能套几个?

3.6与平面和空间打交道的计算几何 

极限情况 

所谓极限情况就是单位圆上有两个点,稍微动一下就会损失一个点,覆盖点最多的圆一定有一个是这种圆(当然当N=1的时候是个例外)。朴素想法是先固定两个点,然后枚举其他的点是否在这两个点决定的两个圆内,朴素得掉渣我就不写了。

更快的算法是,先只固定一个点i,该点的单位圆与其他点j的单位圆相交,形成i圆上的一段弧,该弧被j圆覆盖。最终圆如果在该弧上,则一定能覆盖j点。那么问题归结于找出i圆上被覆盖次数最多的一段弧。

至于弧的表示,用两个极角表示,分别为起始和终止,类似于一个区间。枚举完其他点之后,得到N-1个区间。将其排序后,从前往后扫描,碰到起始计数+1,碰到终止计数-1,同时更新答案。

至于极角的求解,三角函数我全忘光了……查了查维基才记起来,如图:

其中,acos的定义如下:

atan2的定义如下:

那么就可以愉快地写代码了:

#include<cstdio>
#include<cmath>
#include<algorithm>

using namespace std;

#define MAX_N 300 + 16

typedef double p_type;

struct Point
{
	p_type x, y;

	Point(){}

	Point(p_type x, p_type y) : x(x), y(y){}
} ps[MAX_N];

struct PolarAngle
{
	p_type angle;
	bool flag;	// 起点或终点

	const bool operator<(const PolarAngle &other)
	{
		return angle < other.angle;
	}
} as[MAX_N];

inline p_type distance_of(const Point &P, const Point &Q)
{
	return sqrt((P.x - Q.x) * (P.x - Q.x) + (P.y - Q.y) * (P.y - Q.y));
}

inline int solve(const int& n, const p_type& r)
{
	int result = 1;
	for (int i = 0; i < n; ++i)
	{
		int m = 0;
		double d;
		for (int j = 0; j < n; ++j)
		{
			if (i != j && (d = distance_of(ps[i], ps[j])) <= 2)
			{
				double phi = acos(d / 2);
				double theta = atan2(ps[j].y - ps[i].y, ps[j].x - ps[i].x);
				as[m].angle = theta - phi, as[m++].flag = 1;
				as[m].angle = theta + phi, as[m++].flag = 0;
			}
		}
		sort(as, as + m);
		for (int sum = 1, j = 0; j < m; ++j)
		{
			if (as[j].flag)
				++sum;
			else
				--sum;
			result = max(result, sum);
		}
	}
	return result;
}

///////////////////////////SubMain//////////////////////////////////
int main(int argc, char *argv[])
{
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
#endif
	int N;
	while (scanf("%d", &N), N)
	{
		for (int i = 0; i < N; ++i)
		{
			scanf("%lf%lf", &ps[i].x, &ps[i].y);
		}
		printf("%d\n", solve(N, 1.0));
	}
#ifndef ONLINE_JUDGE
	fclose(stdin);
	fclose(stdout);
	system("out.txt");
#endif
	return 0;
}
///////////////////////////End Sub//////////////////////////////////
13872643 hankcs 1981 Accepted 208K 782MS C++ 1686B 2015-02-08 22:55:05

知识共享许可协议 知识共享署名-非商业性使用-相同方式共享码农场 » POJ 1981 Circle and Points 题解 《挑战程序设计竞赛》

分享到:更多 ()

评论 欢迎留言

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

我的开源项目

HanLP自然语言处理包基于DoubleArrayTrie的Aho Corasick自动机