POJ 3943 - Digits on the Floor

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

概要

平面上に n 本の線分があり，いくつかの数字を表している． 0〜9の各数字がそれぞれいくつあるか答える．

制約

解法

重い実装ゲー．

まず数字をなしている線分の集合を求める． 端点で Union-Find した後，線分の途中で接しているケース(3の中央の横棒，4の右側の縦棒，8の中央の横棒)をマージして求めた．

実は

の3つでほとんどの数字は識別できる．

2と5を識別するには，交点ではない端点を求めて，それに続く2つの点が時計回り(2)か反時計回り(5)かを調べればいい．

  1 #include <cstdio>
  2 #include <vector>
  3 #include <map>
  4 #include <set>
  5 #include <complex>
  6 using namespace std;
  7 typedef complex<int> P;
  8 namespace std {
  9   bool operator<(const P& a, const P& b)
 10   {
 11     if (a.real() == b.real()) {
 12       return a.imag() < b.imag();
 13     } else {
 14       return a.real() < b.real();
 15     }
 16   }
 17 };
 18 
 19 inline int cross(const P& a, const P& b) { return a.real()*b.imag() - b.real()*a.imag(); }
 20 
 21 struct segment
 22 {
 23   P a, b;
 24   segment() {}
 25   segment(const P& x, const P& y) : a(x), b(y) {}
 26 
 27   inline bool intersects(const segment& seg) const
 28   {
 29     return
 30       max(a.real(), b.real()) >= min(seg.a.real(), seg.b.real())
 31       && max(seg.a.real(), seg.b.real()) >= min(a.real(), b.real())
 32       && max(a.imag(), b.imag()) >= min(seg.a.imag(), seg.b.imag())
 33       && max(seg.a.imag(), seg.b.imag()) >= min(a.imag(), b.imag())
 34       && static_cast<long long>(cross(seg.b - seg.a, a - seg.a)) * cross(seg.b - seg.a, b - seg.a) <= 0LL
 35       && static_cast<long long>(cross(b - a, seg.a - a)) * cross(b - a, seg.b - a) <= 0LL;
 36   }
 37 };
 38 
 39 bool touch(const segment& s1, const segment& s2)
 40 {
 41   return s1.intersects(s2) && (cross(s1.a-s1.b, s2.a-s1.b) == 0 || cross(s1.a-s1.b, s2.b-s1.b) == 0);
 42 }
 43 
 44 struct DisjointSet/*{{{*/
 45 {
 46   vector<int> parent;
 47 
 48   int root(int x)
 49   {
 50     if (parent[x] < 0) {
 51       return x;
 52     } else {
 53       parent[x] = root(parent[x]);
 54       return parent[x];
 55     }
 56   }
 57 
 58   explicit DisjointSet(int n) : parent(n, -1) {}
 59 
 60   bool unite(int x, int y)
 61   {
 62     const int a = root(x);
 63     const int b = root(y);
 64     if (a != b) {
 65       if (parent[a] < parent[b]) {
 66         parent[a] += parent[b];
 67         parent[b] = a;
 68       } else {
 69         parent[b] += parent[a];
 70         parent[a] = b;
 71       }
 72       return true;
 73     } else {
 74       return false;
 75     }
 76   }
 77 
 78   bool find(int x, int y) { return root(x) == root(y); }
 79   int size(int x) { return -parent[root(x)]; }
 80 };/*}}}*/
 81 
 82 template <class T>
 83 int numbering(map<T,int>& m, const T& x)
 84 {
 85   typename map<T,int>::const_iterator it = m.find(x);
 86   if (it == m.end()) {
 87     const int id = m.size();
 88     m.insert(make_pair(x, id));
 89     return id;
 90   } else {
 91     return it->second;
 92   }
 93 }
 94 
 95 int main()
 96 {
 97   int N;
 98   while (scanf("%d", &N) != EOF && N != 0) {
 99     DisjointSet s(2*N);
100     vector<segment> v;
101     map<P, int> m;
102     for (int i = 0; i < N; i++) {
103       int x1, y1, x2, y2;
104       scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
105       const P p1(x1, y1), p2(x2, y2);
106       const int i1 = numbering(m, p1);
107       const int i2 = numbering(m, p2);
108       s.unite(i1, i2);
109       v.push_back(segment(p1, p2));
110     }
111 
112     vector<vector<segment> > cls;
113     vector<int> done(N, false);
114     for (int i = 0; i < N; i++) {
115       if (!done[i]) {
116         done[i] = true;
117         vector<segment> c(1, v[i]);
118         const int i1 = m[v[i].a];
119         for (int j = i+1; j < N; j++) {
120           const int i3 = m[v[j].a];
121           if (s.find(i1, i3)) {
122             c.push_back(v[j]);
123             done[j] = true;
124           }
125         }
126         cls.push_back(c);
127       }
128     }
129 
130     for (vector<vector<segment> >::iterator it = cls.begin(); it != cls.end();) {
131       if (it->size() == 1) {
132         const segment& s1 = it->front();
133         for (vector<vector<segment> >::iterator jt = cls.begin(); jt != cls.end(); ++jt) {
134           if (jt->size() >= 2) {
135             for (vector<segment>::iterator kt = jt->begin(); kt != jt->end(); ++kt) {
136               if (touch(s1, *kt) || touch(*kt, s1)) {
137                 jt->push_back(it->front());
138                 it = cls.erase(it);
139                 goto NEXT;
140               }
141             }
142           }
143         }
144         ++it;
145   NEXT:
146         ;
147       } else {
148         ++it;
149       }
150     }
151 
152     int ans[10] = {0};
153     for (vector<vector<segment> >::const_iterator it = cls.begin(); it != cls.end(); ++it) {
154       const int L = it->size();
155       map<P,int> m1;
156       int c2 = 0;
157       for (vector<segment>::const_iterator jt = it->begin(); jt != it->end(); ++jt) {
158         const P& p1 = jt->a;
159         const P& p2 = jt->b;
160         ++m1[p1];
161         ++m1[p2];
162         for (vector<segment>::const_iterator kt = it->begin(); kt != it->end(); ++kt) {
163           const P& p3 = kt->a;
164           const P& p4 = kt->b;
165           if (p1 != p3 && p2 != p3 && p1 != p4 && p2 != p4 && touch(*jt, *kt)) {
166             ++c2;
167           }
168         }
169       }
170       const int c1 = m1.size();
171 
172       if (L == 4 && c1 == 4 && c2 == 0) {
173         ++ans[0];
174       } else if (L == 1) {
175         ++ans[1];
176       } else if (L == 5 && c1 == 6 && c2 == 0) {
177         // 2 or 5
178         P p;
179         for (map<P,int>::const_iterator jt = m1.begin(); jt != m1.end(); ++jt) {
180           if (jt->second == 1) {
181             p = jt->first;
182           }
183         }
184         for (vector<segment>::const_iterator jt = it->begin(); jt != it->end(); ++jt) {
185           if (jt->a == p || jt->b == p) {
186             const P& p1 = p;
187             const P& p2 = jt->a == p ? jt->b : jt->a;
188             for (vector<segment>::const_iterator kt = it->begin(); kt != it->end(); ++kt) {
189               const P& p3 = kt->a;
190               const P& p4 = kt->b;
191               if (p2 == p3 && p1 != p4) {
192                 if (cross(p2-p1, p4-p1) < 0) {
193                   ++ans[2];
194                 } else {
195                   ++ans[5];
196                 }
197                 goto DONE;
198               } else if (p2 == p4 && p1 != p3) {
199                 if (cross(p2-p1, p3-p1) < 0) {
200                   ++ans[2];
201                 } else {
202                   ++ans[5];
203                 }
204                 goto DONE;
205               }
206             }
207           }
208         }
209 DONE:
210         ;
211       } else if (L == 4 && c1 == 6 && c2 == 1) {
212         ++ans[3];
213       } else if (L == 3 && c1 == 5 && c2 == 1) {
214         ++ans[4];
215       } else if (L == 5 && c1 == 6 && c2 == 1) {
216         ++ans[6];
217       } else if (L == 3 && c1 == 4 && c2 == 0) {
218         ++ans[7];
219       } else if (L == 5 && c1 == 6 && c2 == 2) {
220         ++ans[8];
221       } else if (L == 4 && c1 == 5 && c2 == 1) {
222         ++ans[9];
223       } else {
224         fprintf(stderr, "BUG!!! L=%d, c1=%d, c2=%d\n", L, c1, c2);
225         for (vector<segment>::const_iterator jt = it->begin(); jt != it->end(); ++jt) {
226           fprintf(stderr, "  segment (%d,%d) - (%d,%d)\n", jt->a.real(), jt->a.imag(), jt->b.real(), jt->b.imag());
227         }
228       }
229     }
230 
231     printf("%d", ans[0]);
232     for (int i = 1; i < 10; i++) {
233       printf(" %d", ans[i]);
234     }
235     putchar('\n');
236   }
237   return 0;
238 }
poj/3943.cc