本質的には彩色数を求めるだけだけど、幾何パートがちょっと面倒...
問題概要
二次元平面上に 個の多角形領域 (すべて単純) がある。各領域はそれぞれある国に属している。異なる多角形領域が同一の国に属していることもある。今、国ごとに「色」を付与したい。ただし、隣接している国には異なる色を割り当てなければならない。
ある 2 つの国が隣接しているとは、それぞれの国を表す多角形の共通部分が「長さが 0 より大きい線分」になることをいう。なお、どの 2 つの国を表す多角形も 0 より大きい領域を共有しないことが保証されている。
今、各国に「色」を割り当てる。隣接している国同士には異なる色を割り当てなければならない。必要な色の個数の最小値を求めよ。
(テストケースがいくつか与えられる)
制約
考えたこと
幾何パートが面倒だけど、要するに
頂点からなるグラフが与えられるので、そのグラフの彩色数を求めよ
という問題である。計算量はよいアルゴリズムを使えば でできるが、他にいろんなアルゴリズムが使えそうである。彩色数のアルゴリズムは以下を参照。
コード
#include <bits/stdc++.h> using namespace std; // 彩色数 long long modpow(long long a, long long n, long long MOD) { long long res = 1; while (n > 0) { if (n & 1) res = res * a % MOD; a = a * a % MOD; n >>= 1; } return res; } int chromatic_number(const vector<vector<int> > &G) { const int MOD = 1000000007; int n = (int)G.size(); vector<int> neighbor(n, 0); for (int i = 0; i < n; ++i) { int S = (1<<i); for (int j = 0; j < n; ++j) if (G[i][j]) S |= (1<<j); neighbor[i] = S; } // I[S] := #. of inndepndet subset of S vector<int> I(1<<n); I[0] = 1; for (int S = 1; S < (1<<n); ++S) { int v = __builtin_ctz(S); I[S] = I[S & ~(1<<v)] + I[S & ~neighbor[v]]; } int low = 0, high = n; while (high - low > 1) { int mid = (low + high) >> 1; // g[S] := #. of "k independent sets" which cover S just // f[S] := #. of "k independent sets" which consist of subseta of S // then // f[S] = sum_{T in S} g(T) // g[S] = sum_{T in S} (-1)^(|S|-|T|)f[T] long long g = 0; for (int S = 0; S < (1<<n); ++S) { if ((n - __builtin_popcount(S)) & 1) g -= modpow(I[S], mid, MOD); else g += modpow(I[S], mid, MOD); g = (g % MOD + MOD) % MOD; } if (g != 0) high = mid; else low = mid; } return high; } // Geometry using DD = double; const DD INF = 1LL<<60; // to be set appropriately const DD EPS = 1e-10; // to be set appropriately const DD PI = acos(-1.0); DD torad(int deg) {return (DD)(deg) * PI / 180;} DD todeg(DD ang) {return ang * 180 / PI;} /* Point */ struct Point { DD x, y; Point(DD x = 0.0, DD y = 0.0) : x(x), y(y) {} friend ostream& operator << (ostream &s, const Point &p) {return s << '(' << p.x << ", " << p.y << ')';} }; inline Point operator + (const Point &p, const Point &q) {return Point(p.x + q.x, p.y + q.y);} inline Point operator - (const Point &p, const Point &q) {return Point(p.x - q.x, p.y - q.y);} inline Point operator * (const Point &p, DD a) {return Point(p.x * a, p.y * a);} inline Point operator * (DD a, const Point &p) {return Point(a * p.x, a * p.y);} inline Point operator * (const Point &p, const Point &q) {return Point(p.x * q.x - p.y * q.y, p.x * q.y + p.y * q.x);} inline Point operator / (const Point &p, DD a) {return Point(p.x / a, p.y / a);} inline Point conj(const Point &p) {return Point(p.x, -p.y);} inline Point rot(const Point &p, DD ang) {return Point(cos(ang) * p.x - sin(ang) * p.y, sin(ang) * p.x + cos(ang) * p.y);} inline Point rot90(const Point &p) {return Point(-p.y, p.x);} inline DD cross(const Point &p, const Point &q) {return p.x * q.y - p.y * q.x;} inline DD dot(const Point &p, const Point &q) {return p.x * q.x + p.y * q.y;} inline DD norm(const Point &p) {return dot(p, p);} inline DD abs(const Point &p) {return sqrt(dot(p, p));} inline DD amp(const Point &p) {DD res = atan2(p.y, p.x); if (res < 0) res += PI*2; return res;} inline bool eq(const Point &p, const Point &q) {return abs(p - q) < EPS;} inline bool operator < (const Point &p, const Point &q) {return (abs(p.x - q.x) > EPS ? p.x < q.x : p.y < q.y);} inline bool operator > (const Point &p, const Point &q) {return (abs(p.x - q.x) > EPS ? p.x > q.x : p.y > q.y);} inline Point operator / (const Point &p, const Point &q) {return p * conj(q) / norm(q);} /* Line */ struct Line : vector<Point> { Line(Point a = Point(0.0, 0.0), Point b = Point(0.0, 0.0)) { this->push_back(a); this->push_back(b); } friend ostream& operator << (ostream &s, const Line &l) {return s << '{' << l[0] << ", " << l[1] << '}';} }; int ccw(const Point &a, const Point &b, const Point &c) { if (cross(b-a, c-a) > EPS) return 1; if (cross(b-a, c-a) < -EPS) return -1; if (dot(b-a, c-a) < -EPS) return 2; if (norm(b-a) < norm(c-a) - EPS) return -2; return 0; } bool isinterPS(const Point &p, const Line &s) { return (ccw(s[0], s[1], p) == 0); } bool isinterSS(const Line &s, const Line &t) { if (eq(s[0], s[1])) return isinterPS(s[0], t); if (eq(t[0], t[1])) return isinterPS(t[0], s); return (ccw(s[0], s[1], t[0]) * ccw(s[0], s[1], t[1]) <= 0 && ccw(t[0], t[1], s[0]) * ccw(t[0], t[1], s[1]) <= 0); } bool issame(Line l, Line s) { for (int it = 0; it < 2; ++it) { if (it == 1) swap(l, s); if ( !eq(l[0], s[0]) && !eq(l[0], s[1]) && ccw(s[0], s[1], l[0]) == 0 ) return true; if ( !eq(l[1], s[0]) && !eq(l[1], s[1]) && ccw(s[0], s[1], l[1]) == 0 ) return true; if ( eq(l[0], s[0]) && eq(l[1], s[1]) ) return true; if ( eq(l[0], s[1]) && eq(l[1], s[0]) ) return true; } return false; } int main() { int N; while (cin >> N, N) { map<string, vector<vector<Point> > > ma; for (int i = 0; i < N; ++i) { string str; cin >> str; vector<Point> vp; int a, b; while (cin >> a) { if (a == -1) break; cin >> b; Point p(a, b); vp.push_back(p); } ma[str].push_back(vp); } int V = ma.size(); vector<vector<int> > G(V, vector<int>(V, 0)); int i = 0, j = 0; for (auto it1 : ma) { j = 0; for (auto it2 : ma) { if (i == j) { ++j; continue; } bool adj = false; for (int x = 0; x < (it1.second).size(); ++x) { for (int y = 0; y < (it2.second).size(); ++y) { vector<Point> vp1 = (it1.second)[x], vp2 = (it2.second)[y]; for (int p = 0; p < vp1.size(); ++p) { for (int q = 0; q < vp2.size(); ++q) { Line l(vp1[p], vp1[ (p+1)%vp1.size() ]); Line m(vp2[q], vp2[ (q+1)%vp2.size() ]); if (issame(l, m)) adj = true; } } } } if (adj) G[i][j] = true; ++j; } ++i; } int res = chromatic_number(G); cout << res << endl; } }
