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 "); } } }