链接:http://codeforces.com/gym/101889
题意
给定N个凸多边形$1 \leq N \leq 14$,每个凸多边形有一条$y=0$和$y=H$的边。将这些多边形在$0 \leq y \leq H$的区域内排成一排,不允许重叠,求最小的总宽度。允许调换多边形的次序,但不能旋转。
题解
首先可以进行一些预处理:将每个多边形向右平移,直到最左边的端点在y轴上,然后将多边形的左半部分和右半部分分离开来。
原问题可以分为明显的两个部分:首先,两两枚举多边形,求出这两个多边形拼起来的收益(即它们各自宽度之和减去拼起来的宽度),然后,在一个完全图上求出最长哈密尔顿路即可。后一个问题用经典的状压dp即可解决,前一个问题则可以用扫描线解决。
注意到两个多边形的接触点必为其中某一个多边形的顶点。因此,只需要处理出两个多边形的所有顶点的y坐标,然后依次求出每个y坐标处可能得到的收益,并去最小值即可。
总复杂度为$O(N^2K + N^2 2^N)$。
代码
#include <bits/stdc++.h> using namespace std; #define rep(i, n) for (int i = 0; i < (n); i++) #define Rep(i, n) for (int i = 1; i <=(n); i++) #define range(x) begin(x), end(x) constexpr double EPS = 1e-8; int fcmp(double x, double y = 0.0) { if (fabs(x - y) < EPS) return 0; return x < y ? -1 : 1; } typedef double T; typedef struct pt { T x, y; T operator,(pt a) { return x * a.x + y * a.y; } // inner product T operator*(pt a) { return x * a.y - y * a.x; } // outer product pt operator+(pt a) { return {x + a.x, y + a.y}; } pt operator-(pt a) { return {x - a.x, y - a.y}; } pt operator*(T k) { return {x * k, y * k}; } pt operator-() { return {-x, -y}; } } vec; typedef pair<pt, pt> seg; int n; int height; struct polygon { int width; vector<pair<int, int>> lpart, rpart; void init(vector<pair<int, int>>& pts) { int minx = INT_MAX, maxx = INT_MIN; for (auto& p : pts) { height = max(height, p.second); minx = min(minx, p.first); maxx = max(maxx, p.first); } width = maxx - minx; for (auto& p : pts) p.first -= minx; int i = 1; while (pts[i].second < height) rpart.push_back(pts[i++]); rpart.push_back(pts[i++]); while (i < pts.size()) lpart.push_back(pts[i++]); lpart.push_back(pts[0]); reverse(range(lpart)); } } poly[16]; pt getMidPoint(pair<int, int> pt1, pair<int, int> pt2, double y) { pt a { (double) pt1.first, (double) pt1.second }, b { (double) pt2.first, (double) pt2.second }; vec v = (b - a) * (1.0 / (b.y - a.y)); return a + v * (y - a.y); } double max_overlap(polygon& polyl, polygon& polyr) { vector<pair<int, int>> &lpts = polyl.rpart, &rpts = polyr.lpart; int ln = lpts.size(), rn = rpts.size(), yn; vector<int> ys; { vector<int> yl(ln), yr(rn); rep (i, ln) yl[i] = lpts[i].second; rep (i, rn) yr[i] = rpts[i].second; set_union(range(yl), range(yr), back_inserter(ys)); yn = ys.size(); } int lptr = 0, rptr = 0; double min_dif = 0.0; rep (i, yn) { pt lp = getMidPoint(lpts[lptr], lpts[lptr+1], ys[i]), rp = getMidPoint(rpts[rptr], rpts[rptr+1], ys[i]); min_dif = max(min_dif, lp.x - rp.x); while (lptr < ln-1 && lpts[lptr+1].second <= ys[i]) lptr++; while (rptr < rn-1 && rpts[rptr+1].second <= ys[i]) rptr++; } return polyl.width - min_dif; } double g[16][16]; double dp[1 << 14][16]; int main() { scanf("%d", &n); rep (i, n) { int k; scanf("%d", &k); vector<pair<int, int>> pts; rep (j, k) { int x, y; scanf("%d%d", &x, &y); pts.emplace_back(x, y); } poly[i].init(pts); } rep (i, n) { rep (j, n) { if (i == j) continue; g[i][j] = max_overlap(poly[i], poly[j]); } } for (unsigned mask = 1; mask < (1 << n); mask++) { if (mask & (mask - 1)) { unsigned rem = mask; while (rem) { unsigned bit = rem & -rem; int i = __builtin_ctz(bit); dp[mask][i] = -1e15; rep (j, n) { if (j == i || ((1 << j) & mask) == 0) continue; dp[mask][i] = max(dp[mask][i], dp[mask ^ bit][j] + g[j][i]); } rem -= bit; } } else { int i = __builtin_ctz(mask); rep (j, n) dp[mask][j] = (j == i ? 0.0 : -1e15); } } double ans = *max_element(range(dp[(1<<n)-1])); double tot = 0.0; rep (i, n) tot += poly[i].width; printf("%.3f\n", tot - ans); return 0; }