http://acm.pku.edu.cn/JudgeOnline/problem?id=1127
Код:
#include <cstdio>
#include <complex>
#include <algorithm>
using namespace std;
typedef complex<int> p_t;
int dot(p_t p, p_t q) { return real(conj(p)*q); }
int det(p_t p, p_t q) { return imag(conj(p)*q); }
int ccw(p_t p1, p_t p2, p_t p3) {
p2 -= p1; p3 -= p1;
if (det(p2, p3) > 0) return 1;
if (det(p2, p3) < 0) return -1;
if (p2.real()*p3.real() < 0 || p2.imag()*p3.imag() < 0) return 1;
if (norm(p2) < norm(p3)) return -1;
return 0;
}
bool intersect(p_t p1, p_t p2, p_t p3, p_t p4) {
return ccw(p1, p2, p3) * ccw(p1, p2, p4) <=0 && ccw(p3, p4, p1) * ccw(p3, p4, p2) <= 0;
}
p_t p[100][2];
bool con[100][100];
int main() {
for (;;) {
int N;
scanf("%d", &N);
if (!N) return 0;
for (int i = 1; i <= N; i++)
for (int j = 0; j < 2; j++) scanf("%d%d", &p[i][j].real(), &p[i][j].imag());
for (int i = 1; i <= N; i++)
for (int j = 1; j <= N; j++) con[i][j] = intersect(p[i][0], p[i][1], p[j][0], p[j][1]);
for (int k = 1; k <= N; k++)
for (int i = 1; i <= N; i++)
for (int j = 1; j <= N; j++) con[i][j] |= (con[i][k] & con[k][j]);
for (;;) {
int a, b;
scanf("%d%d", &a, &b);
if (!(a|b)) break;
printf("%sCONNECTED\n", con[a][b] ? "" : "NOT ");
}
}
}