题目大意
给定矩形中的(n)个点，矩形中的任意一个位置被离它最近的点控制，给出起点，求走出这个矩形最少被几个点控制过。
(n leq 600)
解析
借用网上这张酷炫的图
可以发现，两个点(i,j)的垂直平分线把平面分为两部分，一部分归(i)控制，一部分归(j)控制，而垂直平分线上的点同时被(i,j)控制。
可见，只有经过两区域边界时答案才会增大。
那么把(i)与其它所有点的垂直平分线做一遍半平面交，得到(i)的控制区域，同时也能得到控制区域与(i)相邻的点。
于是我们构建一个图模型，对于控制区域相邻的(i,j)，连一条长度为(1)的边，对于靠着矩形边界的区域，向(n+1)连一条长度为(1)的边。输入数据保证一开始只被一个点控制，这个点一定离它最近，暴力求出来即可，然后跑最短路即可求出答案。
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef double db;
const int N = 1007;
const db eps = 1e-6;
int tot, st[N], to[N * N * 2], nx[N * N * 2];
void add(int u, int v) { to[++tot] = v, nx[tot] = st[u], st[u] = tot; }
int S, T, head, tail, que[N], dis[N];
int spfa()
{
memset(dis, 0, sizeof(dis));
head = 1, que[tail = 1] = S, dis[S] = 1;
while (head <= tail)
{
int u = que[head++];
for (int i = st[u]; i; i = nx[i]) if (!dis[to[i]]) dis[to[i]] = dis[u] + 1, que[++tail] = to[i];
}
return dis[T] - 1;
}
int dcmp(db a, db b) { return fabs(a - b) < eps; }
struct VECTOR
{
db x, y;
VECTOR(db X = 0, db Y = 0) { x = X, y = Y; }
db getang() { return atan2(y, x); }
};
db cross(VECTOR a, VECTOR b) { return a.x * b.y - a.y * b.x; }
VECTOR operator+(VECTOR a, VECTOR b) { return VECTOR(a.x + b.x, a.y + b.y); }
VECTOR operator-(VECTOR a, VECTOR b) { return VECTOR(a.x - b.x, a.y - b.y); }
VECTOR operator*(VECTOR a, db b) { return VECTOR(a.x * b, a.y * b); }
VECTOR operator/(VECTOR a, db b) { return VECTOR(a.x / b, a.y / b); }
typedef VECTOR POINT;
struct LINE
{
POINT s, t;
db ang;
int tag;
LINE() {}
LINE(POINT S, POINT T, int ta) { s = S, t = T, ang = (t - s).getang(), tag = ta; }
};
int operator<(LINE a, LINE b) { return dcmp(a.ang, b.ang) ? cross(b.t - a.s, a.t - a.s) + eps > 0 : a.ang < b.ang; }
POINT inter(LINE a, LINE b) { return a.s + (a.t - a.s) * (cross(b.t - b.s, a.s - b.s) / cross(a.t - a.s, b.t - b.s)); }
int onright(POINT a, LINE b) { return cross(b.t - b.s, a - b.s) < 0; }
db sqr(db a) { return a * a; }
db getdis(db x1, db y1, db x2, db y2) { return sqrt(sqr(x1 - x2) + sqr(y1 - y2)); }
LINE l[N];
int total, n, X0, Y0, X1, Y1, x[N], y[N];
int cnt;
int h, t;
LINE q1[N];
POINT q2[N];
int main()
{
scanf("%d", &total);
while (total--)
{
memset(st, 0, sizeof(st));
memset(nx, 0, sizeof(nx));
scanf("%d%d%d%d%d", &n, &X1, &Y1, &X0, &Y0);
if (!n) { printf("0
"); continue; }
for (int i = 1; i <= n; i++) scanf("%d%d", &x[i], &y[i]);
for (int i = 1; i <= n; i++)
{
cnt = 0;
l[++cnt] = LINE(POINT(0, 0), POINT(X1, 0), n + 1);
l[++cnt] = LINE(POINT(X1, 0), POINT(X1, Y1), n + 1);
l[++cnt] = LINE(POINT(X1, Y1), POINT(0, Y1), n + 1);
l[++cnt] = LINE(POINT(0, Y1), POINT(0, 0), n + 1);
for (int j = 1; j <= n; j++) if (j != i)
{
db mx = 1.0 * (x[i] + x[j]) / 2, my = 1.0 * (y[i] + y[j]) / 2;
db tx = mx + my - y[j], ty = my + x[j] - mx;
l[++cnt] = LINE(POINT(mx, my), POINT(tx, ty), j);
}
sort(l + 1, l + cnt + 1);
h = 1, q1[t = 1] = l[1];
for (int i = 2; i <= cnt; i++)
{
if (dcmp(l[i].ang, l[i - 1].ang)) continue;
while (h < t && onright(q2[t - 1], l[i])) t--;
while (h < t && onright(q2[h], l[i])) h++;
q1[++t] = l[i];
if (h < t) q2[t - 1] = inter(q1[t], q1[t - 1]);
}
while (h < t && onright(q2[t - 1], q1[h])) t--;
while (h < t && onright(q2[h], q1[t])) h++;
if (t - h <= 1) continue;
for (int j = h; j <= t; j++) add(i, q1[j].tag);
}
S = 1;
for (int i = 2; i <= n; i++) if (getdis(x[i], y[i], X0, Y0) < getdis(x[S], y[S], X0, Y0)) S = i;
T = n + 1;
printf("%d
", spfa());
}
return 0;
}