1 // 线段相交 poj 1066  2 // 思路：直接枚举每个端点和终点连成线段，判断和剩下的线段相交个数  3   4 // #include <bits/stdc++.h>  5 #include <iostream>  6 #include <cstdio>  7 #include <cstdlib>  8 #include <algorithm>  9 #include <vector> 10 #include <math.h> 11 using namespace std; 12 #define LL long long 13 typedef pair<int,int> pii; 14 const int inf = 0x3f3f3f3f; 15 const LL MOD =100000000LL; 16 const int N =110; 17 #define clc(a,b) memset(a,b,sizeof(a)) 18 const double eps = 1e-8; 19 void fre() {freopen("in.txt","r",stdin);} 20 void freout() {freopen("out.txt","w",stdout);} 21 inline int read() {int x=0,f=1;char ch=getchar();while(ch>‘9‘||ch<‘0‘) {if(ch==‘-‘) f=-1; ch=getchar();}while(ch>=‘0‘&&ch<=‘9‘) {x=x*10+ch-‘0‘;ch=getchar();}return x*f;} 22  23 int sgn(double x){ 24     if(fabs(x) < eps)return 0; 25     if(x < 0)return -1; 26     else return 1; 27 } 28 struct Point{ 29     double x,y; 30     Point(){} 31     Point(double _x,double _y){ 32         x = _x;y = _y; 33     } 34     Point operator -(const Point &b)const{ 35         return Point(x - b.x,y - b.y); 36     } 37     double operator ^(const Point &b)const{ 38         return x*b.y - y*b.x; 39     } 40     double operator *(const Point &b)const{ 41         return x*b.x + y*b.y; 42     } 43 }; 44  45 struct Line{ 46     Point s,e; 47     int inx; 48     Line(){} 49     Line(Point _s,Point _e){ 50         s=_s;e=_e; 51     } 52 }; 53  54 Line line[N]; 55 bool inter(Line l1,Line l2){ 56     return  57         max(l1.s.x,l1.e.x) >= min(l2.s.x,l2.e.x) && 58         max(l2.s.x,l2.e.x) >= min(l1.s.x,l1.e.x) && 59         max(l1.s.y,l1.e.y) >= min(l2.s.y,l2.e.y) && 60         max(l2.s.y,l2.e.y) >= min(l1.s.y,l1.e.y) && 61         sgn((l2.s-l1.s)^(l1.e-l1.s))*sgn((l2.e-l1.s)^(l1.e-l1.s)) <= 0 && 62         sgn((l1.s-l2.s)^(l2.e-l2.s))*sgn((l1.e-l2.s)^(l2.e-l2.s)) <= 0; 63 } 64  65 vector<Line> list; 66 bool cmp(Line l1,Line l2){ 67     return l1.inx<l2.inx; 68 } 69  70 Point p[110]; 71 int main(){ 72     int n; 73     while(~scanf("%d",&n)){ 74     for(int i=1;i<=n;i++){ 75         double x1,y1,x2,y2; 76         scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2); 77         line[i]=Line(Point(x1,y1),Point(x2,y2)); 78         p[i*2-1]=Point(x1,y1); 79         p[i*2]=Point(x2,y2); 80     } 81     double x1,y1; 82     scanf("%lf%lf",&x1,&y1); 83     Point s=Point(x1,y1); 84     int ans=inf; 85     for(int i=1;i<=2*n;i++){ 86        int tem=0; 87        for(int j=1;j<=n;j++){ 88           if(inter(Line(s,p[i]),line[j])) 89             tem++; 90        } 91        ans=min(ans,tem); 92     } 93      94     Point p1; 95     p1=Point(0,0); 96     int tem=0; 97     for(int i=1;i<=n;i++){ 98         if(inter(Line(s,p1),line[i])) 99           tem++;100     }101     ans=min(ans,tem+1);102     103     p1=Point(0,100);104     tem=0;105     for(int i=1;i<=n;i++){106         if(inter(Line(s,p1),line[i]))107           tem++;108     }109     ans=min(ans,tem+1);110 111     p1=Point(100,0);112      tem=0;113     for(int i=1;i<=n;i++){114         if(inter(Line(s,p1),line[i]))115           tem++;116     }117     ans=min(ans,tem+1);118 119     p1=Point(100,100);120     tem=0;121     for(int i=1;i<=n;i++){122         if(inter(Line(s,p1),line[i]))123           tem++;124     }125     ans=min(ans,tem+1);126     printf("Number of doors = ");127     printf("%d\n",ans);128     }129     return 0;130 }