POJ 3168 - Barn Expansion

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

概要

どの辺も X 軸か Y 軸に平行で，どの頂点も格子点にあるような長方形が N 個与えられる． これらの長方形は互いに重なっていることは無いが，頂点や辺が接していることはある．

どの頂点も辺も，他の長方形の頂点や辺と接していないような長方形はいくつあるか答える．

制約

解法

Y 軸に平行な辺に対して，X 座標と Y 座標の区間に関してソートし，同じ X 座標でかつ Y 座標の区間が重なっている点があるかどうかを調べ，ダメな長方形にマークをつける．

X 軸に平行な辺に対しても同様にチェックし，ダメな長方形にマークをつける．

最後にマークのついていない長方形の数を数えて答える．

 1 #include <cstdio>
 2 #include <algorithm>
 3 using namespace std;
 4 
 5 struct line
 6 {
 7   int id, a, b, c;
 8   bool operator<(const line& l) const
 9   {
10     if (a == l.a) {
11       return b < l.b;
12     } else {
13       return a < l.a;
14     }
15   }
16 };
17 
18 void check(bool *invalid, const line *xs, int N)
19 {
20   for (int i = 0; i < N-1;) {
21     const int a = xs[i].a;
22     const int id = xs[i].id;
23     int end = xs[i].c;
24     for (i++; i < N && xs[i].a == a && xs[i].b <= end; i++) {
25       invalid[id] = invalid[xs[i].id] = true;
26       end = max(end, xs[i].c);
27     }
28   }
29 }
30 
31 int main()
32 {
33   int N;
34   scanf("%d", &N);
35   static line xs[50000], ys[50000];
36   for (int i = 0; i < N; i++) {
37     int a, b, c, d;
38     scanf("%d %d %d %d", &a, &b, &c, &d);
39     line &x1 = xs[2*i], &x2 = xs[2*i+1];
40     x1.id = x2.id = i;
41     x1.b = x2.b = b;
42     x1.c = x2.c = d;
43     x1.a = a;
44     x2.a = c;
45 
46     line &y1 = ys[2*i], &y2 = ys[2*i+1];
47     y1.id = y2.id = i;
48     y1.b = y2.b = a;
49     y1.c = y2.c = c;
50     y1.a = b;
51     y2.a = d;
52   }
53   sort(xs, xs+2*N);
54   sort(ys, ys+2*N);
55 
56   static bool invalid[25000];
57   check(invalid, xs, 2*N);
58   check(invalid, ys, 2*N);
59   int ans = 0;
60   for (int i = 0; i < N; i++) {
61     if (!invalid[i]) {
62       ++ans;
63     }
64   }
65   printf("%d\n", ans);
66   return 0;
67 }
poj/3168.cc