Line Segment Intersection:
1. General Case:
a) (p1, q1, p2) and (p1, q1, q2) have different orientations and
b) (p2, q2, p1) and (p2, q2, q1) have different orientations
2. Special Case
a) (p1, q1, p2), (p1, q1, q2), (p2, q2, p1), and (p2, q2, q1) are all collinear and
b) the x-projections of (p1, q1) and (p2, q2) intersect
c) the y-projections of (p1, q1) and (p2, q2) intersect
To solve the problem floyd warshall algorithm is used.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 |
#include <iostream> using namespace std; struct Point { int x; int y; }; Point P[50]; Point Q[50]; bool gr[50][50]; int orient(Point p,Point q,Point r) { //slope of pq - slope of qr double v = ((p.y-q.y)*(q.x-r.x) - (q.y-r.y)*(p.x-q.x)); if(v==0) return 0; else if(v>0) return 1; else if(v<0) return 2; } bool onlineSeg(Point p,Point q,Point r) { if (r.x <= max(p.x, q.x) && r.x >= min(p.x, q.x) && r.y <= max(p.y, q.y) && r.y >= min(p.y, q.y)) return true; return false; } //y1-mx1-cc =0; bool isConnect(int i,int j) { int a,b,c,d; Point p1,q1,p2,q2; p1 = P[i]; q1 = Q[i]; p2 = P[j]; q2 = Q[j]; a = orient(p1,q1,p2); b = orient(p1,q1,q2); c = orient(p2,q2,p1); d = orient(p2,q2,q1); if(a!=b && c!=d) return 1; if(a == 0 && onlineSeg(p1,q1,p2))//p2 inside of p1q1 return 1; if(b == 0 && onlineSeg(p1,q1,q2))//q2 inside of p1q1 return 1; if(c == 0 && onlineSeg(p2,q2,p1))//q1 inside of p2q2 return 1; if(d == 0 && onlineSeg(p2,q2,q1))//q1 inside of p2q2 return 1; return 0; } int main() { int t,n; double a,b,c,d; bool f=1; cin>>t; while(t--) { cin>>n; for(int i=0;i<n;i++) for(int j=0;j<n;j++) { if(i==j) gr[i][j]=1; else gr[i][j]=0; } for(int i=0;i<n;i++) { cin>>a>>b>>c>>d; P[i].x =a;P[i].y =b; Q[i].x =c;Q[i].y =d; } for(int i=0;i<n;i++) { for(int j=i+1;j<n;j++) { if(isConnect(i,j)) { gr[i][j]=1; gr[j][i]=1; } } } for(int k=0;k<n;k++) { for(int i=0;i<n;i++) { for(int j=0;j<n;j++) { if(!gr[i][j] && i!=j && j!=k) gr[i][j]=gr[i][k] && gr[k][j]; } } } int p,q; int cnt=0; while(cin>>p) { cin>>q; if(p+q==0) break; //cout<<gr[p-1][q-1]<<"\n"; if(!f) { if(cnt==0) cout<<"\n"; cnt =1; } if(gr[p-1][q-1]) cout<<"CONNECTED\n"; else cout<<"NOT CONNECTED\n"; } f = 0; }//while loop return 0; } |