1 #include <iostream>  2 #include<cstdio>  3 #include<cstring>  4 #include<algorithm>  5 #include<stdlib.h>  6 #include<vector>  7 #include<cmath>  8 #include<queue>  9 #include<set> 10 using namespace std; 11 #define N 2210 12 #define LL long long 13 #define INF 0xfffffff 14 const double eps = 1e-10; 15 const double inf = ~0u>>2; 16 vector<int>ed[N]; 17 struct Point 18 { 19     double x,y; 20     Point(double x=0,double y=0):x(x),y(y) {} //构造函数 方便代码编写 21 } p[105],q[N]; 22 int g,dis[N]; 23 bool vis[N]; 24 vector<Point>pi[N]; 25 typedef Point pointt; 26 pointt operator + (Point a,Point b) 27 { 28     return Point(a.x+b.x,a.y+b.y); 29 } 30 pointt operator - (Point a,Point b) 31 { 32     return Point(a.x-b.x,a.y-b.y); 33 } 34 pointt operator * (Point a,double b) 35 { 36     return Point(a.x*b,a.y*b); 37 } 38 pointt operator / (Point a,double b) 39 { 40     return Point(a.x/b,a.y/b); 41 } 42 bool operator < (const Point &a,const Point &b) 43 { 44     return a.x<b.x||(a.x==b.x&&a.y<b.y); 45 } 46 int dcmp(double x) 47 { 48     if(fabs(x)<eps) return 0; 49     else return x<0?-1:1; 50 } 51 double cross(Point a,Point b) 52 { 53     return a.x*b.y-a.y*b.x; 54 } 55 Point intersection1(Point a,Point b,Point c,Point d)//直线交点求解 56 { 57     Point pp = a; 58     double t = ((a.x-c.x)*(c.y-d.y)-(a.y-c.y)*(c.x-d.x))/ 59                ((a.x-b.x)*(c.y-d.y)-(a.y-b.y)*(c.x-d.x)); 60     pp.x+=(b.x-a.x)*t; 61     pp.y+=(b.y-a.y)*t; 62     return pp; 63 } 64 bool seginter(pointt a1,pointt a2,pointt b1,pointt b2) 65 { 66     double c1 = cross(a2-a1,b1-a1),c2 = cross(a2-a1,b2-a1), 67                                         c3 = cross(b2-b1,a1-b1),c4 = cross(b2-b1,a2-b1); 68     return dcmp(c1)*dcmp(c2)<0&&dcmp(c3)*dcmp(c4)<0; 69 } 70 void init(int i,int n) 71 { 72     p[i+1].x = 0; 73     p[i+1].y = 0; 74     p[i+2].x = 0; 75     p[i+2].y = 100; 76     p[i+3].x = 100; 77     p[i+3].y = 100; 78     p[i+4].x = 100; 79     p[i+4].y = 0; 80     p[i+1+n] = p[i+2]; 81     p[i+2+n] = p[i+3]; 82     p[i+3+n] = p[i+4]; 83     p[i+4+n] = p[i+1]; 84  85 } 86 int judge(int x) 87 { 88     if(fabs(q[x].x)<eps||fabs(q[x].y)<eps||fabs(q[x].x-100.0)<eps||fabs(q[x].y-100.0)<eps) 89         return 1; 90     return 0; 91 } 92 void bfs(int st) 93 { 94     queue<int>Q; 95     Q.push(st); 96     memset(vis,0,sizeof(vis)); 97    // cut<< 98     for(int i = 0 ; i <= st ; i++) 99         dis[i] = INF;100     dis[st] = 0;101     while(!Q.empty())102     {103         int u = Q.front();104         Q.pop();105         //printf("%.2f %.2f %d\n",q[u].x,q[u].y,dis[u]);106         if(judge(u))107         {108             printf("Number of doors = %d\n",dis[u]);109             break;110         }111         for(int i =0 ; i < ed[u].size() ; i++)112         {113             int v = ed[u][i];114             //cout<<v<<" "<<dis[u]<<endl;115             dis[v] = min(dis[v],dis[u]+1);116             if(!vis[v])117             {118                 vis[v] = 1;119                 Q.push(v);120             }121         }122     }123 }124 bool cmp(Point a,Point b)125 {126     if(fabs(a.x-b.x)<eps)127         return a.y<b.y;128     return a.x<b.x;129 }130 int main()131 {132     int n,i,j,e;133     scanf("%d",&n);134 //    while(scanf("%d",&n)!=EOF)135 //    {136         n+=4;137         g = 0;138         for(i = 1; i <= n-4 ; i++)139         {140             scanf("%lf%lf%lf%lf",&p[i].x,&p[i].y,&p[i+n].x,&p[i+n].y);141         }142         init(n-4,n);143         for(i = 1; i <= n-4; i++)144         {145             for(j = 1; j <= n-4 ; j++)146             {147                 if(i==j) continue;148                 if(seginter(p[i],p[i+n],p[j],p[j+n]))149                 {150                     pi[i].push_back(intersection1(p[i],p[i+n],p[j],p[j+n]));151                 }152             }153         }154         for(i = 1 ; i <= n-4 ; i++)155         {156             if(dcmp(p[i].x)==0)157                 pi[n-3].push_back(p[i]);158             if(dcmp(p[i+n].x)==0)159                 pi[n-3].push_back(p[i+n]);160             if(dcmp(p[i].y-100)==0)161                 pi[n-2].push_back(p[i]);162             if(dcmp(p[i+n].y-100)==0)163                 pi[n-2].push_back(p[i+n]);164             if(dcmp(p[i].x-100)==0)165                 pi[n-1].push_back(p[i]);166             if(dcmp(p[i+n].x-100)==0)167                 pi[n-1].push_back(p[i+n]);168             if(dcmp(p[i].y)==0)169                 pi[n].push_back(p[i]);170             if(dcmp(p[i+n].y)==0)171                 pi[n].push_back(p[i+n]);172         }173         for(i = 1 ; i <= n; i++)174         {175             pi[i].push_back(p[i]);176             pi[i].push_back(p[i+n]);177             sort(pi[i].begin(),pi[i].end(),cmp);178             for(j = 0 ; j < pi[i].size()-1 ; j++)179             {180                 Point tp;181                 Point p1 = pi[i][j],p2= pi[i][j+1];182                 if(dcmp(p1.x-p2.x)==0&&dcmp(p1.y-p2.y)==0) continue;183                 tp.x = (p1.x+p2.x)/2;184                 tp.y = (p1.y+p2.y)/2;185                 // printf("%d tpx = %.2f tpy = %.2f p1x = %.2f p1y = %.2f p2x = %.2f p2y = %.2f\n",i,tp.x,tp.y,p1.x,p1.y,p2.x,p2.y);186                 q[++g] = tp;187             }188             pi[i].clear();189         }190         g++;191         scanf("%lf%lf",&q[g].x,&q[g].y);192         for(i = 1; i <= g ; i++)193             ed[i].clear();194         for(i = 1; i <= g ; i++)195         {196             //  printf("%.2f %.2f\n",q[i].x,q[i].y);197             for(j = 1; j <= g ; j++)198             {199                 if(i==j) continue;200                 for(e = 1; e <= n; e++)201                 {202                     if(seginter(q[i],q[j],p[e],p[e+n]))203                     {204 //                        if(i==g)205 //                        printf("%.2f %.2f e = %d\n",q[j].x,q[j].y,e);206                         break;207                     }208                 }209                 if(e>n)210                 {211 //                    if(i==g)212 //                    printf("%.2f %.2f %.2f %.2f\n",q[i].x,q[i].y,q[j].x,q[j].y);213                     ed[i].push_back(j);214                 }215             }216         }217         bfs(g);218 //    }219     return 0;220 }

 1 #include <iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<stdlib.h> 6 #include<vector> 7 #include<cmath> 8 #include<queue> 9 #include<set>10 using namespace std;11 #define N 221012 #define LL long long13 #define INF 0xfffffff14 const double eps = 1e-10;15 const double inf = ~0u>>2;16 vector<int>ed[N];17 struct Point18 {19     double x,y;20     Point(double x=0,double y=0):x(x),y(y) {} //构造函数 方便代码编写21 } p[105],q[N];22 int g,dis[N];23 bool vis[N];24 vector<Point>pi[N];25 typedef Point pointt;26 pointt operator + (Point a,Point b)27 {28     return Point(a.x+b.x,a.y+b.y);29 }30 pointt operator - (Point a,Point b)31 {32     return Point(a.x-b.x,a.y-b.y);33 }34 pointt operator * (Point a,double b)35 {36     return Point(a.x*b,a.y*b);37 }38 pointt operator / (Point a,double b)39 {40     return Point(a.x/b,a.y/b);41 }42 bool operator < (const Point &a,const Point &b)43 {44     return a.x<b.x||(a.x==b.x&&a.y<b.y);45 }46 int dcmp(double x)47 {48     if(fabs(x)<eps) return 0;49     else return x<0?-1:1;50 }51 double cross(Point a,Point b)52 {53     return a.x*b.y-a.y*b.x;54 }55 bool seginter(pointt a1,pointt a2,pointt b1,pointt b2)56 {57     double c1 = cross(a2-a1,b1-a1),c2 = cross(a2-a1,b2-a1),58                                         c3 = cross(b2-b1,a1-b1),c4 = cross(b2-b1,a2-b1);59     return dcmp(c1)*dcmp(c2)<0&&dcmp(c3)*dcmp(c4)<0;60 }61 int main()62 {63     int n,i,j,e;64     scanf("%d",&n);65     g = 0;66     for(i = 1; i <= n ; i++)67     {68         scanf("%lf%lf%lf%lf",&p[i].x,&p[i].y,&p[i+n].x,&p[i+n].y);69     }70     Point tp;71     scanf("%lf%lf",&tp.x,&tp.y);72     if(n==0)73     {74         puts("Number of doors = 1");75         return 0;76     }77     int ans = INF;78     for(i = 1 ; i <= n*2; i++)79     {80         int ts = 1;81         for(j = 1 ; j <= n ; j++)82         {83             if(seginter(p[i],tp,p[j],p[j+n]))84                 ts++;85         }86         ans = min(ans,ts);87     }88     printf("Number of doors = %d\n",ans);89     return 0;90 }