POJ 2296 - Map Labeler

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

概要

\(m\) 個の格子点 \((X_i, Y_i)\) が与えられる。 各格子点の上か下のいずれかに一定のサイズの縦横がそれぞれ軸に並行な長方形のラベルをつける。 ただし、ラベル同士が被らないように配置したい。 このとき、ラベルのサイズの最大値 (整数) を答える。

制約

• \(3 \le m \le 100\)
• \(- 10 ^ 4 \le X_i, Y_i \le 10 ^ 4\)

解法

あるサイズ \(S\) で被らずに配置できれば、それ以下の任意のサイズでも配置でき、 またあるサイズ \(S'\) では配置できなければ、それ以上の任意のサイズでも配置できないので、 サイズ \(S\) に関する二分探索が使える。

\(i\) 番目の格子点の上にラベルを配置することを \(x_{2i}\)、下に配置することを \(x_{2i+1}\) と表すと、 すべての \(i\) に対して

• \(x_{2i} \lor x_{2i+1}\)

が成立しなければならない。 また、あるサイズ \(S\) において \(x_k\) と \(x_l\) が被る場合、

• \(\lnot x_k \lor \lnot x_l\)

が成立しなければならない。

これらの条件式は 2-SAT なので解ける。

  1 #include <cstdio>
  2 #include <vector>
  3 #include <stack>
  4 using namespace std;
  5 
  6 void scc_visit(const vector<vector<int> >& g, int v, vector<int>& scc_map, int& scc_size,/*{{{*/
  7     stack<int>& stk, vector<bool>& in_stk, vector<int>& low, vector<int>& num, int& time)
  8 {
  9   low[v] = num[v] = ++time;
 10   stk.push(v);
 11   in_stk[v] = true;
 12   for (vector<int>::const_iterator it(g[v].begin()); it != g[v].end(); ++it) {
 13     const int u = *it;
 14     if (num[u] == 0) {
 15       scc_visit(g, u, scc_map, scc_size, stk, in_stk, low, num, time);
 16       low[v] = min(low[v], low[u]);
 17     } else if (in_stk[u]) {
 18       low[v] = min(low[v], num[u]);
 19     }
 20   }
 21   if (low[v] == num[v]) {
 22     for (;;) {
 23       const int u = stk.top();
 24       stk.pop();
 25       in_stk[u] = false;
 26       scc_map[u] = scc_size;
 27       if (u == v) {
 28         break;
 29       }
 30     }
 31     ++scc_size;
 32   }
 33 }/*}}}*/
 34 
 35 // O(V+E)
 36 pair<vector<int>,int> strongly_connected_components(const vector<vector<int> >& g)/*{{{*/
 37 {
 38   const int N = g.size();
 39   vector<int> num(N), low(N);
 40   stack<int> stk;
 41   vector<bool> in_stk(N, false);
 42   int time = 0;
 43   vector<int> scc_map(N);
 44   int scc_size = 0;
 45   for (int v = 0; v < N; v++) {
 46     if (num[v] == 0) {
 47       scc_visit(g, v, scc_map, scc_size, stk, in_stk, low, num, time);
 48     }
 49   }
 50   return make_pair(scc_map, scc_size);
 51 }/*}}}*/
 52 
 53 // 2-SAT
 54 bool sat(const vector<vector<int> >& g)
 55 {
 56   const pair<vector<int>, int> p = strongly_connected_components(g);
 57   const int N = g.size()/2;
 58   vector<vector<int> > has(p.second, vector<int>(N, false));
 59   for (int i = 0; i < N; i++) {
 60     has[p.first[i]][i] = true;
 61   }
 62   for (int i = N; i < 2*N; i++) {
 63     if (has[p.first[i]][i-N]) {
 64       return false;
 65     }
 66   }
 67   return true;
 68 }
 69 
 70 struct rect
 71 {
 72   double left, right, below, above;
 73   rect(double a, double b, double c, double d)
 74     : left(a), right(b), below(c), above(d) {}
 75 
 76   bool intersects(const rect& r) const
 77   {
 78     if (right <= r.left) {
 79       return false;
 80     }
 81     if (r.right <= left) {
 82       return false;
 83     }
 84     if (above <= r.below) {
 85       return false;
 86     }
 87     if (r.above <= below) {
 88       return false;
 89     }
 90     return true;
 91   }
 92 };
 93 
 94 bool ok(int size, const vector<pair<int,int> >& v)
 95 {
 96   const int N = v.size();
 97   vector<rect> rs;
 98   for (vector<pair<int,int> >::const_iterator it = v.begin(); it != v.end(); ++it) {
 99     rs.push_back(rect(it->first - size/2.0, it->first + size/2.0, it->second, it->second + size));
100     rs.push_back(rect(it->first - size/2.0, it->first + size/2.0, it->second - size, it->second));
101   }
102 
103   vector<vector<int> > g(4*N);
104   for (int i = 0; i < N; i++) {
105     g[2*i+2*N].push_back(2*i+1);
106     g[2*i+1+2*N].push_back(2*i);
107   }
108   for (int i = 0; i < N; i++) {
109     for (int j = i+1; j < N; j++) {
110       for (int k = 0; k < 4; k++) {
111         static const int di[] = {0, 0, 1, 1}, dj[] = {0, 1, 0, 1};
112         const int s = 2*i + di[k], t = 2*j + dj[k];
113         if (rs[s].intersects(rs[t])) {
114           g[s].push_back(t+2*N);
115           g[t].push_back(s+2*N);
116         }
117       }
118     }
119   }
120   return sat(g);
121 }
122 
123 int main()
124 {
125   int T;
126   scanf("%d", &T);
127   while (T-- > 0) {
128     int N;
129     scanf("%d", &N);
130     vector<pair<int,int> > v(N);
131     for (int i = 0; i < N; i++) {
132       scanf("%d %d", &v[i].first, &v[i].second);
133     }
134 
135     int lo = 1, hi = 100000;
136     while (lo < hi) {
137       const int mid = (lo + hi + 1)/2;
138       if (ok(mid, v)) {
139         lo = mid;
140       } else {
141         hi = mid-1;
142       }
143     }
144     printf("%d\n", lo);
145   }
146   return 0;
147 }