계산 기하학 + 검색 집합 처리: POJ 1127 Jack Straws

POJ 1127 문제 의 대 의 는 다음 과 같다.
n 개의 작은 막대기 가 2 차원 평면 에 분포 되 어 있 고 모든 작은 막대기 가 양쪽 의 좌 표를 표시 했다. 작은 막대기 의 번 호 는 1 ～ n 이다. 현재 의 문 제 는 두 개의 작은 막대기 의 번 호 를 제시 하여 연결 되 어 있 는 지 물 어 보 는 것 이다.
여기 서 연 결 된 정 의 는 직접 연결 하거나 여러 개의 다른 작은 막대 기 를 통 해 간접 적 으로 연결 할 수 있다 는 것 이다.
두 개의 작은 막대기 의 교차 상황 (예 를 들 어 그들의 교점 좌 표를 직접 구 하 는 것) 을 직접 연구 할 수 없고 벡터 를 고려 할 수 있다.
벡터 에서 벡터 P1 = S1 - T1, P2 = S2 - T2 (모든 변 수 는 벡터) 를 가정 하면 교차 여 부 를 고려 하 는 것 은 (평행 을 고려 하지 않 는 것) 과 같다.
1) 두 벡터 가 대표 하 는 직선 교차점 이 Q 라 고 가정 하고 이때 Q 에 대응 하 는 벡터 가 Q 라 고 가정 하면 벡터 P1 과 Q 의 관 계 는 Q = T1 + (S1 - T1) * a (a 는 하나의 계수) 이다.
2) 벡터 P2 에 대해 차 승의 각도 에서: (S2 - T2) X (Q - T2) = 0;
3) 상기 두 방정식 을 연결 하면 a = (T2 - S2) X (T1 - T2) / [(S2 - T2) X (S1 - T1)] 를 구 할 수 있 고 Q 의 좌표 도 나온다.
4) Q 가 P1 과 P2 를 대표 하 는 선분 위 에 있 는 지, 아니면 벡터 를 사용 하 는 지 를 토론 합 니 다. 이때 Q 가 선분 안에 있 으 면 (두 개의 점 포함) 다음 과 같 습 니 다. (Q - S1) * (Q - T1) < = 0 & & (Q - S2) * (Q - T2) < = 0;
다음은 평행 상황 을 토론 한다.
만약 에 두 개의 벡터 가 평행 하 는 동시에 이들 이 서로 포함 되 는 지 (즉, 겹 치 는 일부분 이 있 는 지) 를 토론 하려 면 사실은 특정한 선분 의 특정한 점 이 다른 선분 안에 있 는 지 논증 하 는 것 이다. 그래서 네 가지 상황 이 있 을 것 이다. 여기 서 논술 을 생략 하 는 것 이다.
이런 처 리 를 한 후에 바로 연 결 된 나무 막대 기 를 알 게 되 었 다. 그 다음 에 간접 적 으로 연 결 된 나무 막대 기 는 사실은 폐쇄 문 제 를 전달 하 는 것 이 므 로 Warshall 알고리즘 을 사용 하거나 집합 을 찾 을 수 있다.
1. 기 하 + Warshall 계산, 복잡 도 O (N ^ 3) 712 K / 79MS 수락

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath>

using namespace std;
const int maxn = 15;
const double EPS = 1e-10;

int n;
bool grap[maxn][maxn];
//    
double add(double a, double b) {
	if (abs(a + b) < EPS*(abs(a) + abs(b))) return 0;
	return a + b;
}

struct Point {
	double x, y;
	Point(){};
	Point(double x, double y): x(x), y(y){}
	Point operator + (Point p) {
		return Point(add(x, p.x), add(y, p.y));
	}
	Point operator - (Point p) {
		return Point(add(x, -p.x), add(y, -p.y));
	}
	Point operator * (double p) {
		return Point(x*p, y*p);
	}
	//  
	double dot(Point p) {
		return add(x*p.x, y*p.y);
	}
	//  
	double det(Point p) {
		return add(x*p.y, -y*p.x);
	}
};
Point s[maxn], t[maxn];
// q     st 
bool on_seg(Point& s, Point& t, Point& q) {
	return (s - q).det(t - q) == 0 && (q - s).dot(q - t) <= 0;
}
//   
Point intersection(Point& s1, Point& t1, Point& s2, Point& t2) {
	return t1 + (s1 - t1)*((t2 - s2).det(t1 - t2) / (s2 - t2).det(s1 - t1));
}

void init() {
	for (int i = 1; i <= n; i++) {
		grap[i][i] = true;
		for (int j = 1; j < i; j++) {
			if ((s[i] - t[i]).det(s[j] - t[j]) == 0) {
				grap[i][j] = grap[j][i] = on_seg(s[i], t[i], s[j]) || on_seg(s[i], t[i], t[j]) || on_seg(s[j], t[j], s[i]) || on_seg(s[j], t[j], t[i]);
			}
			else {
				Point temp = intersection(s[i], t[i], s[j], t[j]);
				grap[i][j] = grap[j][i] = on_seg(s[i], t[i], temp) && on_seg(s[j], t[j], temp);
			}
		}
	}
	//Warshall Algorithm
	for (int k = 1; k <= n; k++) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				grap[i][j] |= grap[i][k] && grap[k][j];
			}
		}
	}
}

int main() {
	int a, b;
	while (scanf("%d", &n) && n != 0) {
		for (int i = 1; i <= n; i++) scanf("%lf %lf %lf %lf", &s[i].x, &s[i].y, &t[i].x, &t[i].y);
		init();
		while (scanf("%d %d", &a, &b) && a*b != 0) printf(grap[a][b] ? "CONNECTED
" : "NOT CONNECTED
");
	}
	return 0;
}

2. 기 하 + 를 계산 하고 집합 을 찾 습 니 다: O (N ^ 2) + O (log (N)) Accept 721 K / 47MS

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <cstring>

using namespace std;
const int maxn = 15;
const double EPS = 1e-10;

int n;
int flag[maxn];//             
int Rank[maxn];//         
bool grap[maxn][maxn];

double add(double a, double b) {
	if (abs(a + b) < EPS*(abs(a) + abs(b))) return 0;
	return a + b;
}

struct Point {
	double x, y;
	Point(){};
	Point(double x, double y): x(x), y(y){}
	Point operator + (Point p) {
		return Point(add(x, p.x), add(y, p.y));
	}
	Point operator - (Point p) {
		return Point(add(x, -p.x), add(y, -p.y));
	}
	Point operator * (double p) {
		return Point(x*p, y*p);
	}
	double dot(Point p) {
		return add(x*p.x, y*p.y);
	}
	double det(Point p) {
		return add(x*p.y, -y*p.x);
	}
};
Point s[maxn], t[maxn];

bool on_seg(Point& s, Point& t, Point& q) {
	return (s - q).det(t - q) == 0 && (q - s).dot(q - t) <= 0;
}

Point intersection(Point& s1, Point& t1, Point& s2, Point& t2) {
	return t1 + (s1 - t1)*((t2 - s2).det(t1 - t2) / (s2 - t2).det(s1 - t1));
}
//     
int findRoot(int x) {
	if (flag[x] == x) return x;
	return flag[x] = findRoot(flag[x]);
}
//     （ ）
void unite(int x, int y) {
	x = findRoot(x);
	y = findRoot(y);
	if (x == y) return;
	if (Rank[x] < Rank[y]) flag[x] = flag[y];
	else {
		flag[y] = flag[x];
		if (Rank[x] == Rank[y]) Rank[x]++;
	}
}

void init() {
	for (int i = 1; i <= n; i++) flag[i] = i;
	for (int i = 1; i <= n; i++) {
		grap[i][i] = true;
		for (int j = 1; j < i; j++) {
			if ((s[i] - t[i]).det(s[j] - t[j]) == 0) {
				grap[i][j] = grap[j][i] = on_seg(s[i], t[i], s[j]) || on_seg(s[i], t[i], t[j]) || on_seg(s[j], t[j], s[i]) || on_seg(s[j], t[j], t[i]);
			}
			else {
				Point temp = intersection(s[i], t[i], s[j], t[j]);
				grap[i][j] = grap[j][i] = on_seg(s[i], t[i], temp) && on_seg(s[j], t[j], temp);
			}
			if (grap[i][j]) unite(i, j);
		}
	}
}

int main() {
	int a, b;
	memset(Rank, 0, sizeof(Rank));
	while (scanf("%d", &n) && n != 0) {
		for (int i = 1; i <= n; i++) scanf("%lf %lf %lf %lf", &s[i].x, &s[i].y, &t[i].x, &t[i].y);
		init();
		while (scanf("%d %d", &a, &b) && a*b != 0) printf(findRoot(a) == findRoot(b) ? "CONNECTED
" : "NOT CONNECTED
");
	}
	return 0;
}