题目描述
髙考又来了，对于不认真读书的来讲真不是个好消息为了小杨能在家里认真读书，他 的亲戚决定驻扎在他的家里监督他学习，有爷爷奶奶、外公外婆、大舅、大嫂、阿姨......
小杨实在是忍无可忍了，这种生活跟监狱有什么区别！为了他亲爱的小红，为了他的 dota,他决定越狱！
假设小杨的家是个n*m的矩阵，左下角坐标为（0, 0)，右上角坐标为（xl, yl)。小 杨有n个亲戚，驻扎在矩阵里（位置不同，且不在矩阵的边上）。小杨家里的每个地方都被 亲戚监控着，而且只被距离最近的亲戚监控：
也就是说假设小杨所在的位置是（3,3),亲戚A在（3,0), A距离小杨距离是3；亲戚 B在（6,7),则B距离小杨距离是5。距离A<距离B，所以（3,3)位置由A监控。
如果“最近距离”出现同时有几个亲戚，那么那个位置同时被那几个亲戚监控。
给出小杨的坐标（x0，y0)。因为被发现的人数越少，越狱成功的机会越大，所以小杨需 耍你设计一条越狱路线到达矩形的边上，且被发现的人数最少。
Ps:小杨做的方向是任意的，也就是说路线上的任意位置H需耍是实数。
保证一开始小杨只被一个亲戚监控着。
输入格式
第一行 一个正整数t<=3表示数据个数
接下来t个数据：
第一行n表示亲戚个数
第二行4个正整数表示举行右上角坐标(x1,y1)和小杨的坐标(x0,y0)
接下来n行，每行2个正整数表示一个亲戚的位置
输出格式
每个数据一个正整数表示越狱被发现人数的最小值
输入输出样例
输入 #1
2
4
10 10 5 5
5 6
3 5
7 5
5 3
17
14 12 7 6
7 11
6 9
7 7
1 10
2 20
1 6
2 6
1 1
2 2
5 1
5 2
13 1
12 2
12 7
13 7
12 11
13 11输出 #1
1
2说明/提示
数据解释:
第一个数据， 小杨直接往上走，只被 (5,6) 监控过.
第二个数据，小杨被 (7,7) 监控- 走到 (9,9) 被 (7,11) 监控， 然后直接往上走.
数据规模:
前 50%数据. n<=200;
其余数据 n<=600.
求出每个亲戚与其他亲戚的垂直平分线 ， 这些垂直平分线以及矩形的四周 ， 构成了半平面交的凸包
将每个半平面交求出 ， 然后将他与他相邻的亲戚连边 ， 边权为 1 ， 跑最短路，
这题就是重在建图，也就是求出每个亲戚的管辖范围
注意
1.有一些在矩形外的亲戚
2.特判一下 \(n = 0\) 的情况
3.求交点的函数 ， 一定要想清楚 ， 实在不行就记住 ，
inline point meetline(Line A , Line B)
{
if(dcmp(cross(A.v , B.v)) == 0) return (point){0 , 0};
point k = A.p - B.p;
return A.p + A.v * (cross(B.v , k) / cross(A.v , B.v));
}前者减去后者
返回前者乘上比率 ， 比率是后者 * k 与总面积的比值
4.onright 函数
传入cross 的是直线的方向而不是直线的端点
return dcmp(cross(A - B.p , B.v))// AC
return dcmp(cross(A - B.p , B.p))// WA 5.注意判断条件 是用来 \(if\) 还是 \(continue\) 的
if(no[i] || j == i) countinue;
if(!no[i] && j != i) { do .... }6.多测清空
注意 dcmp 的传入参数的类型 一定一定是 double
总之 ， 注意细节！！
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<algorithm>
using namespace std;
const int N = 1000;
const double eps = 1e-8;
inline int read()
{
register int x = 0; register char c = getchar();
while(c < '0' || c > '9') c = getchar();
while(c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0' , c = getchar();
return x;
}
int n , X0 , Y0 , X1 , Y1 , s , tot , cnt;
int head[N] , no[N];
struct edge{int v , nex;} e[N*N];
inline int dcmp(double x) { return fabs(x) < eps ? 0 : (x < 0 ? -1 : 1); }
void add(int u , int v)
{
e[++cnt].v = v; e[cnt].nex = head[u]; head[u] = cnt;
e[++cnt].v = u; e[cnt].nex = head[v]; head[v] = cnt;
return ;
}
struct point{
double x , y;
point(double x = 0 , double y = 0) : x(x) , y(y) {}
point operator + (const point &A) const {return point(x + A.x , y + A.y);}
point operator - (const point &A) const {return point(x - A.x , y - A.y);}
point operator * (const double &K) const { return point(x * K , y * K); }
double operator * (const point &A) const {return x * A.x + y * A.y; }
}a[N] , p[N];
struct Line{
point p , v; int id; double ang;
Line(point p = point() , point v = point() , int id = 0): p(p) , v(v), id(id) { ang = atan2(v.y , v.x); }
bool operator < (const Line &A) const { return ang < A.ang; }
}l[N] , sta[N];
double cross(point A , point B) { return A.x * B.y - A.y * B.x; }
double dot(point A) { return A.x * A.x + A.y * A.y; }
double dis(point A , point B) { return sqrt((A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y));}
inline bool onright(point A , Line B) { return dcmp(cross(A - B.p , B.v)) > 0; } // !!!!
inline point meetline(Line A , Line B)
{
if(dcmp(cross(A.v , B.v)) == 0) return (point){0 , 0};
point k = A.p - B.p;
return A.p + A.v * (cross(B.v , k) / cross(A.v , B.v));
}
point rot(point A) { return point(-A.y , A.x); }
Line get_mid_line(point A , point B , int i) // A 和 B 的垂直平分线
{
point p = point((A.x + B.x) / 2 , (A.y + B.y) / 2);
return Line(p , rot(B - A) , i);
}
void init(int id)
{
tot = 0;
l[++tot] = Line(point(0 , 0) , point(1 , 0) , n + 1);
l[++tot] = Line(point(X1 , 0) , point(0 , 1) , n + 1);
l[++tot] = Line(point(X1 , Y1) , point(-1 , 0) , n + 1);
l[++tot] = Line(point(0 , Y1) , point(0 , -1) , n + 1);
for(int i = 1 ; i <= n ; ++i) if(i != id && !no[i]) // !!!
l[++tot] = get_mid_line(a[id] , a[i] , i);
return ;
}
void calc(int id)
{
int n = tot , tail , head;
sort(l + 1 , l + 1 + n); sta[head = tail = 1] = l[1];
for(int i = 2 ; i <= n ; ++i)
{
while(head < tail && onright(p[tail-1] , l[i])) tail--;
while(head < tail && onright(p[head] , l[i])) head++;
sta[++tail] = l[i];
if(dcmp(cross(sta[tail].v , sta[tail-1].v)) == 0)
{
tail--;
if(onright(sta[tail].p , l[i])) sta[tail] = l[i];
}
if(head < tail) p[tail-1] = meetline(sta[tail] , sta[tail-1]);
}
while(head < tail && onright(p[tail-1] , sta[head])) tail--;
if(head >= tail) return ;
p[tail] = meetline(sta[head] , sta[tail]);
for(int i = head ; i <= tail ; ++i) add(id , sta[i].id);
return ;
}
int d[N] , vis[N];
int spfa(int s)
{
queue<int> q; q.push(s);
for(int i = 1 ; i <= n + 1 ; ++i) d[i] = 1e9 , vis[i] = 0;
d[s] = 0;
while(q.size())
{
int x = q.front(); q.pop(); vis[x] = 0;
for(int i = head[x] ; i ; i = e[i].nex)
{
int v = e[i].v;
if(d[v] > d[x] + 1)
{
d[v] = d[x] + 1;
if(!vis[v]) vis[v] = 1 , q.push(v);
}
}
}
return d[n+1];
}
void clear() // 多测清空
{
memset(head , 0 , sizeof head); cnt = 0;
memset(no , 0 , sizeof no);
return ;
}
int main()
{
int T = read();
while(T --> 0)
{
n = read();
X1 = read(); Y1 = read(); X0 = read(); Y0 = read();
if(n == 0) { puts("0"); continue; }
double minn = 1e50 , len = 1e50;
for(int i = 1 , x , y ; i <= n ; ++i)
{
x = read() , y = read() , a[i] = point(1.0 * x , 1.0 * y);
if(x > X1 || y > Y1) no[i] = 1;
len = dis(a[i] , point(X0 , Y0));
if(len < minn) minn = len , s = i;
}
//printf("---------------------\n%d\n--------------------------\n" , s);
for(int i = 1 ; i <= n ; ++i)
{
if(no[i]) continue;
init(i); calc(i);
}
printf("%d\n" , spfa(s));
clear();
}
return 0;
}
/*
2
4
10 10 5 5
5 6
3 5
7 5
5 3
17
14 12 7 6
7 11
6 9
7 7
1 10
2 20
1 6
2 6
1 1
2 2
5 1
5 2
13 1
12 2
12 7
13 7
12 11
13 11
*/