uva 10691 - Subway(区间选点）

题目链接：uva 10691 - Subway

题目大意：给定n个点，要求建造尽量少得铁路（从原点发射出的射线），使得所有点到铁路的最短距离小于d。

解题思路：题目可以转化成区间选点问题，即以极角来表示铁轨，然后计算出每个区间可行的极角范围，进行区间选点。

注意：（1）如果点到原点的距离dis<=d的话，不进行考虑，也无法判断，因为没有说直角边大于等于斜边的。

（2）区间有可能在二三象限时重叠，我的处理方法是每次枚举起始点，进行n次选点问题。

（3）因为每次都将区间i的左右区间+2pi后放到最后，忘记考虑s[i].r+2pi 有可能小于 s[m-1].r的情况，所以一直WA。

处理，在初始化区间时，将右区间大于pi的统一左右区间减掉2pi。

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm>

using namespace std;
const int N = 205;
const int INF = 0x3f3f3f3f;
const double pi = acos(-1.0);
const double eps = 1e-9;

struct state {
	double l, r;
}s[N*2];

int n, m;
double d;

bool cmp(const state& a, const state& b) {
	return a.r - b.r < eps;
}

void init () {
	double x, y, c, k;

	m = 0;
	scanf("%d%lf", &n, &d);
	for (int i = 0; i < n; i++) {
		scanf("%lf%lf", &x, &y);
		c = atan2(y, x);
		double dis = sqrt(x*x + y*y);
		if (d >= dis) continue;
		k = asin(d/dis);
		s[m].l = c-k; s[m].r = c+k;
		if (s[m].r > pi) {
			s[m].l -= 2*pi;
			s[m].r -= 2*pi;
		}
		m++;
	}
	sort(s, s + m, cmp);
	for (int i = 0; i < m; i++) {
		s[i+m].l = s[i].l + 2*pi;
		s[i+m].r = s[i].r + 2*pi;
	}
}

int del (state* f) {
	int ans = 1;
	double tmp = f[0].r;
	for (int i = 1; i < m; i++) {
		if (tmp - f[i].l > -eps) continue;
		else {
			tmp = f[i].r;
			ans++;
		}
	}
	return ans;
}

int solve () {
	if (m == 0) return 0;

	int ans = m;
	for (int i = 0; i < m; i++) {
		ans = min(del(s+i), ans);
	}
	return ans;
}

int main () {
	int cas;
	scanf("%d", &cas);
	while (cas--) {
		init();
		printf("%d\n", solve());
	}
	return 0;
}