本文共 4045 字，大约阅读时间需要 13 分钟。
题意：给出若干个没有公共面积的多边形，几个多边形可能属于同一个国家，要求给这个地图染色，同一个国家用相同的颜色，相邻国家不能用相同颜色。问最少需要多少种颜色。
分析：计算几何+搜索。先判断哪些多边形是相邻的(这里只有一个公共点的不算相邻)。对于两个多边形，两两比较他们所有的边，看是否有重合部分。建好图后，枚举颜色数量（也可二分查找），并判断这些颜色是否可行。判断过程用搜索。搜索的方法是，n个点，第一层确定第一个点的颜色，第二层确定第二个点的颜色，以此类推，每次要向下递归前先判断当前染色是否产生冲突。而不是向二分图染色那样染搜相邻的点。
#include #include #include #include using namespace std;#define zero(x) (((x)>0?(x):-(x)) 0 ? 1 : -1;}struct Edge{ int v; int length; Edge() {} Edge(int v, int length):v(v), length(length) {}};struct Point{ double x,y; Point() {} Point(double x, double y):x(x), y(y) {} Point operator - (const Point &a) const { return Point(x - a.x, y - a.y); } bool operator == (const Point &a) const { return x == a.x && y == a.y; }};double cross_product(Point a, Point b){ return a.x * b.y - b.x * a.y;}double cross_product(Point p0, Point p1, Point p2){ return cross_product(p1 - p0, p2 - p0);}double dot_product(Point a, Point b){ return a.x * b.x + a.y * b.y;}double dot_product(Point p0, Point p1, Point p2){ return dot_product(p1 - p0, p2 - p0);}struct Line{ Point a, b; Line() {} Line(Point a, Point b):a(a), b(b) {} bool operator == (const Line &l) const { return l.a == a && l.b == b; }};bool points_inline(Point p1, Point p2, Point p3){ return zero(cross_product(p1, p2, p3));}bool same_side(Point p1, Point p2, Line l){ return cross_product(l.a, p1, l.b) * cross_product(l.a, p2, l.b) > eps;}bool point_online_in(Point p, Line l){ return zero(cross_product(p, l.a, l.b)) && double_cmp(dot_product(p, l.a, l.b)) < 0;}bool overlap(Line u, Line v){ if (u == v || (u.a == v.b && u.b == v.a)) return true; if (!points_inline(u.a, u.b, v.a) || !points_inline(u.a, u.b, v.b)) return false; bool ret = point_online_in(u.a, v); ret = ret || point_online_in(u.b, v); ret = ret || point_online_in(v.a, u); ret = ret || point_online_in(v.b, u); return ret;}struct Polygon{ Point point[MAX_POINT_NUM]; int id; int point_num;}polygon[MAX_POLYGON_NUM];map territory_id;int polygon_num;int territory_cnt;int color[MAX_POLYGON_NUM];bool graph[MAX_TERR_NUM][MAX_TERR_NUM];void input(){ territory_id.clear(); territory_cnt = 0; for (int i = 0; i < polygon_num; i++) { char territory_name[25]; scanf("%s", territory_name); string name = string(territory_name); if (territory_id.find(name) == territory_id.end()) { territory_id[name] = ++territory_cnt; } polygon[i].point_num = 0; polygon[i].id = territory_id[name]; while (1) { int j = polygon[i].point_num; scanf("%lf", &polygon[i].point[j].x); if (polygon[i].point[j].x == -1) break; scanf("%lf", &polygon[i].point[j].y); polygon[i].point_num++; } }}bool neighbour(Polygon &a, Polygon &b){ for (int i = 0; i < a.point_num; i++) { for (int j = 0; j < b.point_num; j++) { Line l1 = Line(a.point[i], a.point[(i + 1) % a.point_num]); Line l2 = Line(b.point[j], b.point[(j + 1) % b.point_num]); if (overlap(l1, l2)) return true; } } return false;}void create_graph(){ memset(graph, 0, sizeof(graph)); for (int i = 0; i < polygon_num - 1; i++) { for (int j = i + 1; j < polygon_num; j++) { int a = polygon[i].id; int b = polygon[j].id; a--; b--; if (a == b || graph[a][b]) continue; if (neighbour(polygon[i], polygon[j])) graph[a][b] = graph[b][a] = true; } }}bool ok(int u){ for (int i = 0; i < territory_cnt; i++) if (i != u && graph[i][u]) { if (color[u] == color[i]) return false; } return true;}bool dfs(int color_num, int u){ if (u == territory_cnt) { return true; } for (int i = 0; i < color_num; i++) { color[u] = i; if (!ok(u)) continue; if (dfs(color_num, u + 1)) return true; } color[u] = -1; return false;}int main(){ while (scanf("%d", &polygon_num), polygon_num) { input(); create_graph(); int ans = 0; while (ans <= 10) { ans++; memset(color, -1, sizeof(color)); color[0] = 0; if (dfs(ans, 1)) { printf("%d\n", ans); break; } } } return 0;}
转载地址：http://xrrml.baihongyu.com/
