【计算几何】ZOJ_1041 SP898 Transmitters

题意

给出一个半径为$r$r的半圆形的圆心坐标，求出它最多能覆盖的点。

思路

首先我们可以先把超出圆的半径的点排除掉。
然后我们每次枚举一个点为中间的分割线，把这个平面分成两边，我们利用叉积求出左边和右边的点的个数，求最大值就好了。

代码

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

int n, ans;
double xx, xy, xr;
double x[151], y[151];

double CP(double x, double y, double a, double b, double c, double d) {
	return (b - y) * (c - x) - (a - x) * (d - y);
}

double dis(double x, double y, double a, double b) {
	return sqrt((x - a) * (x - a) + (b - y) * (b - y));
}

int main() {
	while (1) {
		scanf("%lf %lf %lf", &xx, &xy, &xr);
		if (xr < 0) return 0;
		scanf("%d", &n);
		int p = 0;
		for (int i = 1; i <= n; i++) {
			p++;
			scanf("%lf %lf", &x[p], &y[p]);
			if (dis(x[p], y[p], xx, xy) > xr)//排除无用点
				p--;
		}
		ans = 0;
		for (int i = 1; i <= p; i++) {
			int left = 0, right = 0;
			for (int j = 1; j <= p; j++) {
				double cj = CP(xx, xy, x[i], y[i], x[j], y[j]);
				if (cj <= 0) left++;
				if (cj >= 0) right++;
			}
			ans = std::max(ans, std::max(left, right));
		}
		printf("%d\n", ans);
	}
}