题目链接：https://vjudge.net/problem/POJ-1066
题意：给出一些直线，直线与直线切割的线段是围墙，只能从围墙中间穿过，问最少穿过几层墙才能到达终点
看了hzwer的，觉得好有道理，虽然说是中点，但其实直接求每个端点就ok了
1 /************************************************************************* 2 > File Name: poj1066.cpp 3 # File Name: poj1066.cpp 4 # Author : xiaobuxie 5 # QQ : 760427180 6 # Email:[email protected] 7 # Created Time: 2019年09月21日 星期六 15时11分27秒 8 ************************************************************************/ 9 10 #include<iostream> 11 #include<cstdio> 12 #include<map> 13 #include<cmath> 14 #include<cstring> 15 #include<set> 16 #include<queue> 17 #include<vector> 18 #include<algorithm> 19 using namespace std; 20 typedef long long ll; 21 #define inf 0x3f3f3f3f 22 #define pq priority_queue<int,vector<int>,greater<int> > 23 const double eps = 1e-8; 24 const int N=50; 25 int sgn(double x){ 26 if(fabs(x)<eps) return 0; 27 if(x<0) return -1; 28 return 1; 29 } 30 struct Point{ 31 double x,y; 32 Point operator - (const Point& b)const{ 33 return (Point){x-b.x,y-b.y}; 34 } 35 double operator ^ (const Point& b)const{ 36 return x*b.y-b.x*y; 37 } 38 }P[N<<2]; 39 struct Line{ 40 Point s,e; 41 }L[N]; 42 bool inter(Line l1,Line l2){ 43 return 44 max(l1.s.x,l1.e.x) >= min(l2.s.x,l2.e.x) && 45 max(l2.s.x,l2.e.x) >= min(l1.s.x,l1.e.x) && 46 max(l1.s.y,l1.e.y) >= min(l2.s.y,l2.e.y) && 47 max(l2.s.y,l2.e.y) >= min(l1.s.y,l1.e.y) && 48 sgn((l2.s-l1.s)^(l1.e-l1.s))*sgn((l2.e-l1.s)^(l1.e-l1.s)) <= 0 && 49 sgn((l1.s-l2.s)^(l2.e-l1.s))*sgn((l1.e-l2.s)^(l2.e-l2.s)) <= 0; 50 } 51 int main(){ 52 int n; scanf("%d",&n); 53 if(!n){ 54 printf("Number of doors = 1"); 55 return 0; 56 } 57 double x1,x2,y1,y2,ex,ey; 58 for(int i=1;i<=n;++i){ 59 scanf("%lf %lf %lf %lf",&x1,&y1,&x2,&y2); 60 L[i]=(Line){(Point){x1,y1},(Point){x2,y2}}; 61 P[i*2]=(Point){x1,y1}; P[i*2-1]=(Point){x2,y2}; 62 } 63 scanf("%lf %lf",&ex,&ey); 64 Point ed=(Point){ex,ey}; 65 int ans=10000000; 66 for(int i=1;i<=2*n;++i){ 67 Line l1=(Line){ed,P[i]}; 68 int tem=0; 69 for(int j=1;j<=n;++j){ 70 if(i==2*j || i==2*j-1) continue; 71 if(inter(l1,L[j])) ++tem; 72 } 73 ans=min(ans,tem); 74 //cerr<<ans<<endl; 75 } 76 //cerr<<ans<<endl; 77 printf("Number of doors = %d",ans+1); 78 return 0; 79 }