?? 1102.cpp
字號:
/* This Code is Submitted by wywcgs for Problem 1102 on 2005-12-14 at 17:17:50 */
#include <cstdio>
#include <cstring>
const int MAX = 16;
class UFSet {
private:
int parent[MAX];
public:
void makeSet();
int find(int);
void unionSet(int, int);
};
void UFSet::makeSet() {
memset(parent, -1, sizeof(parent));
}
int UFSet::find(int x) {
if(parent[x] == -1) {
return x;
} else {
parent[x] = find(parent[x]);
return parent[x];
}
}
void UFSet::unionSet(int x, int y) {
int pX = find(x);
int pY = find(y);
if(pX != pY) {
parent[pX] = pY;
}
}
class Stick {
private:
class Point {
public:
int x, y;
};
int min(int x, int y) const {
return x < y ? x : y;
}
int max(int x, int y) const {
return x > y ? x : y;
}
public:
Point b, e;
void scan();
bool covered(const Stick&) const;
};
void Stick::scan() {
scanf("%d %d %d %d", &b.x, &b.y, &e.x, &e.y);
}
bool Stick::covered(const Stick& s) const {
if(min(e.x, b.x) > max(s.e.x, s.b.x)) {
return false;
} else if(min(s.e.x, s.b.x) > max(e.x, b.x)) {
return false;
} else if(min(e.y, b.y) > max(s.e.y, s.b.y)) {
return false;
} else if(min(s.e.y, s.b.y) > max(e.y, b.y)) {
return false;
} else {
int a = (s.b.y-e.y)*(b.x-e.x)-(b.y-e.y)*(s.b.x-e.x);
int p = (s.e.y-e.y)*(b.x-e.x)-(b.y-e.y)*(s.e.x-e.x);
int c = (b.y-s.e.y)*(s.b.x-s.e.x)-(s.b.y-s.e.y)*(b.x-s.e.x);
int d = (e.y-s.e.y)*(s.b.x-s.e.x)-(s.b.y-s.e.y)*(e.x-s.e.x);
return (a * p <= 0 && c * d <= 0);
}
}
int main()
{
UFSet ufs;
Stick stick[MAX];
int n, i, j;
while(scanf("%d", &n) != EOF && n != 0) {
ufs.makeSet();
for(i = 0; i < n; i++) {
stick[i].scan();
}
for(i = 0; i < n; i++) {
for(j = i+1; j < n; j++) {
if(stick[i].covered(stick[j])) {
ufs.unionSet(i, j);
}
}
}
int a, b;
while(scanf("%d %d", &a, &b) != EOF && a*b != 0) {
if(ufs.find(a-1) == ufs.find(b-1)) {
printf("CONNECTED\n");
} else {
printf("NOT CONNECTED\n");
}
}
}
return 0;
}
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -