# bzoj3199 [Sdoi2013]escape

2018/03/06 19:18

n=0卡了我一下午//////

  1 #include <cstdio>
2 #include <cstring>
3 #include <iostream>
4 #include <algorithm>
5 #include <cmath>
6 #define N 666
7 #define eps 1e-12
8 using namespace std;
9 int g[N][N];
10 struct point{
11     double x[2];
12     point(){}
13     point(double a,double b){x[0]=a,x[1]=b;}
14     double & operator [] (int a){return x[a];}
15 }p[N];
16 double dis(point a,point b){
17     return sqrt((b[0]-a[0])*(b[0]-a[0])+(b[1]-a[1])*(b[1]-a[1]));
18 }
19 struct line{
20     double a,b,c,k;
21     int id;
22     line(){}
23     line (double x,double y,double z,int pos){
24         a=x;b=y;c=z;
25         k=atan2(-x,y);id=pos;
26     }
27     void rev(){
28         a=-a;b=-b;c=-c;
29         k=atan2(-a,b);
30     }
31 }l[N],q[N];
32 int T,n,bot,tot,top,be,ans;
33 double wx,wy,sx,sy,d;
34 bool cmp(line a,line b){
35     if(fabs(a.k-b.k)<eps)return a.c<b.c;
36     return a.k<b.k;
37 }
38 point cross(line a,line b){
39     double x=(b.c*a.b-a.c*b.b)/(a.a*b.b-a.b*b.a);
40     double y=(b.c*a.a-a.c*b.a)/(a.b*b.a-a.a*b.b);
41     return point(x,y);
42 }
43 bool judge(point a,line b){
44     return a[0]*b.a+a[1]*b.b+b.c<-eps;
45 }
46 void addline (point a,point b,int id){
47     point c=point((a[0]+b[0])/2,(a[1]+b[1])/2);
48     if(a[0]==b[0])l[++tot]=line(0.0,1.0,-c[1],id);
49     else if(a[1]==b[1])l[++tot]=line(1.0,0.0,-c[0],id);
50     else l[++tot]=line(1.0,(b[1]-a[1])/(b[0]-a[0]),-c[0]-(b[1]-a[1])/(b[0]-a[0])*c[1],id);
51     if(judge(a,l[tot]))l[tot].rev();
52 }
53 void work(int x){
54     register int i,j;
55     sort(l+1,l+tot+1,cmp);
56     for(i=2,j=1;i<=tot;i++)
57         if(fabs(l[i].k-l[j].k)>=eps)l[++j]=l[i];
58     tot=j;
59     bot=1;top=2;
60     q[1]=l[1];q[2]=l[2];
61     for(i=3;i<=tot;i++){
62         while(bot<top&&judge(cross(q[top-1],q[top]),l[i]))top--;
63         while(bot<top&&judge(cross(q[bot+1],q[bot]),l[i]))bot++;
64         q[++top]=l[i];
65     }
66     while(bot<top&&judge(cross(q[top-1],q[top]),q[bot]))top--;
67     for(i=bot;i<=top;i++){
68         if(q[i].id)g[x][q[i].id]=g[q[i].id][x]=1;
69         else g[x][n+1]=g[n+1][x]=0;
70     }
71 }
72 int main(){
73     scanf("%d",&T);
74     while(T--){
75         scanf("%d",&n);
76         if(!n){puts("0");continue;}
77         memset(g,0x3f,sizeof g);
78         scanf("%lf%lf%lf%lf",&wx,&wy,&sx,&sy);
79         for(int i=1;i<=n;i++)
80             scanf("%lf%lf",&p[i][0],&p[i][1]);
81         for(int i=1;i<=n;i++){
82             tot=0;
83             for(int j=1;j<=n;j++)if(j!=i)
89             work(i);
90         }
91         d=g[0][0];ans=0;
92         for(int i=1;i<=n;i++){
93             double now=dis(point(sx,sy),p[i]);
94             if(now<d)d=now,be=i;
95         }
96         for(int k=1;k<=n+1;k++)
97             for(int i=1;i<=n+1;i++)
98                 for(int j=1;j<=n+1;j++)
99                     g[i][j]=min(g[i][j],g[i][k]+g[k][j]);
100         ans=g[be][n+1]+1;
101         printf("%d\n",ans);
102     }
103     return 0;
104 }
View Code

0
0 收藏

0 评论
0 收藏
0