POJ 1127 - Jack Straws

http://poj.org/problem?id=1127

概要

n 本のわらが二次元座標上に置かれている． このとき，いくつかの「a 本目のわらと b 本目のわらが繋がっているか」というクエリに答える．

わらは間接的に繋がっていることもある． つまり，わら a, b, c について，a と b が繋がっていて b と c が繋がっているとき，a と c も繋がっている．

制約

解法

線分の交差判定 + Union-Find．

線分の交差判定を間違えて 1WA してしまった (線分同士が同一直線上でかつ交わっていないケースを忘れていた)．

 1 #include <iostream>
 2 #include <vector>
 3 #include <complex>
 4 using namespace std;
 5 typedef complex<int> P;
 6 
 7 class DisjointSet/*{{{*/
 8 {
 9   private:
10     vector<int> parent;
11 
12     int root(int x)
13     {
14       if (parent[x] < 0) {
15         return x;
16       } else {
17         parent[x] = root(parent[x]);
18         return parent[x];
19       }
20     }
21 
22   public:
23     explicit DisjointSet(int n) : parent(n, -1) {}
24 
25     bool unite(int x, int y)
26     {
27       const int a = root(x);
28       const int b = root(y);
29       if (a != b) {
30         if (parent[a] < parent[b]) {
31           parent[a] += parent[b];
32           parent[b] = a;
33         } else {
34           parent[b] += parent[a];
35           parent[a] = b;
36         }
37         return true;
38       } else {
39         return false;
40       }
41     }
42 
43     bool find(int x, int y) { return root(x) == root(y); }
44     int size(int x) { return -parent[root(x)]; }
45 };/*}}}*/
46 
47 inline int cross(const P& a, const P& b) { return a.real()*b.imag() - b.real()*a.imag(); }
48 
49 struct segment
50 {
51   P a, b;
52   segment() {}
53   segment(const P& x, const P& y) : a(x), b(y) {}
54 
55   inline bool intersects(const segment& seg) const
56   {
57     return
58       max(a.real(), b.real()) >= min(seg.a.real(), seg.b.real())
59       && max(seg.a.real(), seg.b.real()) >= min(a.real(), b.real())
60       && max(a.imag(), b.imag()) >= min(seg.a.imag(), seg.b.imag())
61       && max(seg.a.imag(), seg.b.imag()) >= min(a.imag(), b.imag())
62       && cross(seg.b - seg.a, a - seg.a) * cross(seg.b - seg.a, b - seg.a) <= 0
63       && cross(b - a, seg.a - a) * cross(b - a, seg.b - a) <= 0;
64   }
65 };
66 
67 int main()
68 {
69   int N;
70   while (cin >> N && N != 0) {
71     vector<segment> segs;
72     for (int i = 0; i < N; i++) {
73       int x1, y1, x2, y2;
74       cin >> x1 >> y1 >> x2 >> y2;
75       segs.push_back(segment(P(x1, y1), P(x2, y2)));
76     }
77     DisjointSet s(N);
78     for (int i = 0; i < N; i++) {
79       for (int j = 0; j < i; j++) {
80         if (segs[i].intersects(segs[j])) {
81           s.unite(i, j);
82         }
83       }
84     }
85 
86     int a, b;
87     while (cin >> a >> b && !(a == 0 && b == 0)) {
88       --a;  --b;
89       cout << (s.find(a, b) ? "" : "NOT ") << "CONNECTED" << endl;
90     }
91   }
92   return 0;
93 }
poj/1127.cc