POJ 1389 - Area of Simple Polygons

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

概要

与えられた N 個の長方形によって覆われる面積を答える．

制約

• 1 <= N <= 1000
• 0 <= 座標 <= 50000

解法

長方形の左右の x 座標で区間を区切り，各区間に存在する長方形に対して y 座標を調べて面積を足していけばいい．

 1 #include <iostream>
 2 #include <vector>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 struct rect
 7 {
 8   int lx, ly, rx, ry;
 9   bool operator<(const rect& that) const
10   {
11     return ly < that.ly;
12   }
13 };
14 
15 int main()
16 {
17   rect r;
18   while (cin >> r.lx >> r.ly >> r.rx >> r.ry && r.lx != -1) {
19     vector<rect> rs(1, r);
20     vector<int> xs;
21     xs.push_back(r.lx);
22     xs.push_back(r.rx);
23     while (cin >> r.lx >> r.ly >> r.rx >> r.ry && r.lx != -1) {
24       rs.push_back(r);
25       xs.push_back(r.lx);
26       xs.push_back(r.rx);
27     }
28 
29     sort(rs.begin(), rs.end());
30     sort(xs.begin(), xs.end());
31     const vector<int>::const_iterator last = unique(xs.begin(), xs.end());
32     long long ans = 0LL;
33     vector<int>::const_iterator it = xs.begin();
34     for (vector<int>::const_iterator jt = it++; it != last; ++it, ++jt) {
35       const long long w = *it - *jt;
36       int l = -1, h = -1;
37       for (vector<rect>::const_iterator kt = rs.begin(); kt != rs.end(); ++kt) {
38         if (kt->lx <= *jt && *it <= kt->rx) {
39           if (l == -1) {
40             h = kt->ry;
41             l = kt->ly;
42           } else if (kt->ly <= h) {
43             h = max(h, kt->ry);
44           } else {
45             ans += w * (h-l);
46             h = kt->ry;
47             l = kt->ly;
48           }
49         }
50       }
51       if (l != -1) {
52         ans += w * (h-l);
53       }
54     }
55     cout << ans << endl;
56   }
57   return 0;
58 }