Creator's World

一、前言

本篇题解借鉴了网上的一些思路，并非自己想出来的。在这里只是提供一种不同的方法，也为了加深自己对计算几何的理解。

二、题意

给定一个圆的圆心坐标 $(x,y)$ 以及半径 $r$，再给出 $n$ 个点的坐标。求在这个圆内选择一个半圆，使得半圆覆盖的点数最多。

三、思路

首先我们去除没意义的冗杂信息，在这里显然离圆心距离大于半径的点都不需要考虑，因为它们不可能被覆盖。

然后对于剩下的点，我们发现被半圆覆盖的点实际上满足的是 它们相对于圆心的极角差最大不超过 $180^。$。关于什么是极角，可以参考 百度百科。那我们就有个想法了：将所有点按它们相对于圆心的极角从小到大排序，然后枚举每一个点，将点看作序列，答案就是序列中最长的满足极角差不超过 $180^。$ 的子串（即连续区间）。可以用类似双端队列的东西来维护。时间复杂度为 $O(n\log n)$。

至于如何求极角，C++ 中有个 $\operatorname{atan2}$ 函数。$\operatorname{atan2}(y,x)$ 求的就是 $(x,y)$ 的极角。

不过还要注意，因为有两个方向：顺时针和逆时针，为了避免答案遗漏，我们要将所有点都复制一遍，复制的极角都加上 $360^。$。因为 C++ 用的是弧度制，$360^。=2\times \pi$，所以要加上 $2\times \pi$。

四、代码

#include<bits/stdc++.h>
#define ln puts("")
using namespace std;
typedef long long ll;
typedef long double ld;
 
inline ll read() {
	ll sum = 0, ff = 1;
	char ch = getchar();
	while(ch < '0' || ch > '9') {
		if(ch == '-')
			ff = -1;
		ch = getchar();
	}
	while(ch >= '0' && ch <= '9')
		sum = sum * 10 + ch - '0', ch = getchar();
	return sum * ff;
}

const ld PI = acos(-1);
const ld eps = 1e-18;
const int N = 1e3 + 7;
ld x, y, r;
int n, he, cnt, ans;
struct node {
	ld deg;
	bool operator< (const node &x) const {
		return deg - x.deg < eps;//相当于 deg < x.deg 
	}
}a[N];

ld dis(ld x1, ld y1, ld x2, ld y2) {
	return (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);	
}

int main() {
//	freopen("", "r", stdin);
//	freopen("", "w", stdout);
	while(scanf("%Lf%Lf%Lf", &x, &y, &r) && r >= 0.0) {
		ans = cnt = 0;
		he = 1;
		n = read();
		for(int i = 1; i <= n; i++) {
			ld nx, ny;
			scanf("%Lf%Lf", &nx, &ny);
			if(dis(nx, ny, x, y) - r * r <= eps)//相当于 dis(nx, ny, x, y) <= r * r 
				a[++cnt].deg = atan2(ny - y, nx - x);//求相对于原点的极角
		}
		for(int i = 1; i <= cnt; i++)
			a[i + cnt].deg = a[i].deg + 2 * PI;
		cnt *= 2;
		sort(a + 1, a + 1 + cnt);
		for(int i = 1; i <= cnt; i++)
			if(a[i].deg - a[he].deg - PI > eps)//相当于 a[i].deg - a[he].deg > PI 
				ans = max(ans, i - he), he++;
		cout << ans, ln;
	}
	return 0;
}