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