POJ 2473 - Decorate the wall

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

概要

\(W \times H\) の壁に \(n\) 個の長方形の絵がかけられている。 ここに、さらにもうひとつ \(w \times h\) の絵をかけたい。 このとき、絵をかけられるときはその左上の座標を、かけられないときは「Fail!」と答える。 ただしかけられる座標が複数存在するときは、y 座標が最も小さいもの (それも複数存在するときは x 座標が最も小さいもの) を答える。

制約

• \(0 \le n \le 200\)
• \(1 \le w, h \le 10 ^ 6\)

解法

絵をかける場所の x 座標の候補は x = 0 か、既にある絵のすぐ右である。 同様に、y 座標の候補は y = 0 か、既にある絵のすぐ上である。 すると、候補の数は高々 \((n+1) ^ 2\) 個しかなく、その場所にかけられるかどうかは \(O(n)\) でチェックできるので全体で \(O(n ^ 3)\) で解ける。

 1 #include <cstdio>
 2 #include <algorithm>
 3 using namespace std;
 4 
 5 struct rect
 6 {
 7   int x1, y1, x2, y2;
 8   rect() {}
 9   rect(int a, int b, int c, int d) : x1(a), y1(b), x2(c), y2(d) {}
10   bool in_x(int x) const { return x1 < x && x < x2; }
11   bool in_y(int y) const { return y1 < y && y < y2; }
12   bool has_common(const rect& r) const
13   {
14     return !(x2 <= r.x1 || r.x2 <= x1 || y2 <= r.y1 || r.y2 <= y1);
15   }
16 };
17 
18 bool check(int W, int H, int N, const rect *rs, const rect& r)
19 {
20   if (r.x2 > W || r.y2 > H) {
21     return false;
22   }
23   for (int i = 0; i < N; i++) {
24     if (rs[i].has_common(r)) {
25       return false;
26     }
27   }
28   return true;
29 }
30 
31 int main()
32 {
33   int T;
34   scanf("%d", &T);
35   while (T-- > 0) {
36     int N, W, H;
37     scanf("%d %d %d", &N, &W, &H);
38     static rect rs[1000];
39     static int xs[1001], ys[1001];
40     for (int i = 0; i < N; i++) {
41       scanf("%d %d %d %d", &rs[i].x1, &rs[i].y1, &rs[i].x2, &rs[i].y2);
42       xs[i] = rs[i].x2;
43       ys[i] = rs[i].y2;
44     }
45     xs[N] = ys[N] = 0;
46     int w, h;
47     scanf("%d %d", &w, &h);
48     sort(xs, xs+N+1);
49     sort(ys, ys+N+1);
50     for (int i = 0; i <= N; i++) {
51       for (int j = 0; j <= N; j++) {
52         if (check(W, H, N, rs, rect(xs[j], ys[i], xs[j]+w, ys[i]+h))) {
53           printf("%d %d\n", xs[j], ys[i]);
54           goto FINISH;
55         }
56       }
57     }
58     puts("Fail!");
59 FINISH:
60     ;
61   }
62   return 0;
63 }