POJ 1231 - The Alphabet Game

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

概要

二次元上に k 種類のアルファベットをそれぞれ p 個書かれている． 何本か直線を引いて，同じ領域には同じアルファベットが p 個すべて含まれるように分割できるかどうかを答える．

制約

解法

同じアルファベットすべてを囲むような長方形を考えると，条件を満たすような直線はその長方形の辺に沿ったもので，他の長方形を分割しないようなものになる． そのような直線すべてで分割して，最終的に k 個の領域になっていれば YES，そうでなければ NO．

  1 #include <iostream>
  2 #include <vector>
  3 using namespace std;
  4 
  5 struct rect
  6 {
  7   int left, right, top, bottom;
  8 };
  9 
 10 vector<vector<rect> > cut_horiz(const vector<vector<rect> >& a, int x)
 11 {
 12   vector<vector<rect> > b;
 13   for (vector<vector<rect> >::const_iterator it(a.begin()); it != a.end(); ++it) {
 14     vector<rect> l, r;
 15     for (vector<rect>::const_iterator jt(it->begin()); jt != it->end(); ++jt) {
 16       if (jt->left < x && x < jt->right) {
 17         // contains
 18         return a;
 19       } else if (x <= jt->left) {
 20         // kt is right
 21         r.push_back(*jt);
 22       } else {
 23         // kt is left
 24         l.push_back(*jt);
 25       }
 26     }
 27     if (!l.empty()) {
 28       b.push_back(l);
 29     }
 30     if (!r.empty()) {
 31       b.push_back(r);
 32     }
 33   }
 34   return b;
 35 }
 36 
 37 vector<vector<rect> > cut_vert(const vector<vector<rect> >& a, int y)
 38 {
 39   vector<vector<rect> > b;
 40   for (vector<vector<rect> >::const_iterator it(a.begin()); it != a.end(); ++it) {
 41     vector<rect> u, l;
 42     for (vector<rect>::const_iterator jt(it->begin()); jt != it->end(); ++jt) {
 43       if (jt->bottom < y && y < jt->top) {
 44         // contains
 45         return a;
 46       } else if (y <= jt->bottom) {
 47         // kt is upper
 48         u.push_back(*jt);
 49       } else {
 50         // kt is lower
 51         l.push_back(*jt);
 52       }
 53     }
 54     if (!u.empty()) {
 55       b.push_back(u);
 56     }
 57     if (!l.empty()) {
 58       b.push_back(l);
 59     }
 60   }
 61   return b;
 62 }
 63 
 64 int main()
 65 {
 66   int T;
 67   cin >> T;
 68   while (T-- > 0) {
 69     int K, P;
 70     cin >> K >> P;
 71     vector<rect> v;
 72     for (int i = 0; i < K; i++) {
 73       rect r;
 74       r.left = r.bottom = 100000000;
 75       r.right = r.top = 0;
 76       for (int j = 0; j < P; j++) {
 77         int x, y;
 78         cin >> x >> y;
 79         r.left = min(r.left, x-1);
 80         r.right = max(r.right, x);
 81         r.bottom = min(r.bottom, y-1);
 82         r.top = max(r.top, y);
 83       }
 84       v.push_back(r);
 85     }
 86 
 87     vector<vector<rect> > a(1, v);
 88     for (vector<rect>::const_iterator it(v.begin()); it != v.end(); ++it) {
 89       a = cut_horiz(a, it->left);
 90       a = cut_horiz(a, it->right);
 91       a = cut_vert(a, it->top);
 92       a = cut_vert(a, it->bottom);
 93     }
 94     if (a.size() == K) {
 95       cout << "YES" << endl;
 96     } else {
 97       cout << "NO" << endl;
 98     }
 99   }
100   return 0;
101 }
poj/1231.cc