链接：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;
}