Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
ccw 1A代码#include <stdio.h> #include <algorithm> #include <iostream> using namespace std; struct point{ long long x, y; }; typedef point vector; struct segment{ point a, b; }k[20]; int cross(vector v1, vector v2){ return (v1.x*v2.y - v2.x*v1.y); } int dot(vector v1, vector v2){ return (v1.x*v2.x + v1.y*v2.y); } long long norm(vector v){ return v.x*v.x + v.y*v.y; } int ccw(point p0, point p1, point p2){ vector p1p0; p1p0.x = p1.x - p0.x; p1p0.y = p1.y - p0.y; vector p2p0; p2p0.x = p2.x - p0.x; p2p0.y = p2.y - p0.y; int crossv = cross(p1p0, p2p0); if(crossv > 0) return -1; else if(crossv < 0) return 1; else{ int dotv = dot(p2p0, p1p0); if(dotv < 0) return 1; else{ long long normv = norm(p2p0) - norm(p1p0); //cout << norm(p2p0) << " " << normv << endl; if(normv > 0) return -1; else return 0; } } } int intersect(point p1, point p2, point p3, point p4){ return (ccw(p1, p2, p3) * ccw(p1, p2, p4) <= 0 && ccw(p3, p4, p1) * ccw(p3, p4, p2) <= 0 ); } bool intersection(segment s1, segment s2){ return intersect(s1.a, s1.b, s2.a, s2.b); } bool g[15][15]; int main(){ int n; while(cin >> n){ if(n == 0) break; for(int i = 1; i <= n; i++){ cin >> k[i].a.x >> k[i].a.y >> k[i].b.x >> k[i].b.y; } for(int i = 1; i <= n; i++){ for(int j = 1; j <= n; j++) g[i][j] = false; g[i][i] = true; } for(int i = 1; i <= n; i++){ for(int j = 1; j <= n; j++) if(intersection(k[i], k[j])) g[i][j] = true; } for(int k = 1; k <= n; k++) for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) g[i][j] = g[i][j] || g[i][k] && g[k][j]; int e, f; while(cin >> e >> f){ if(e == 0 && f == 0) break; if(g[e][f]) cout << "CONNECTED\n"; else cout << "NOT CONNECTED\n"; } } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator