| ||||||||||
| 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