# [2017-2018 ACM-ICPC Latin American Regional Programming Contest] A. Arranging tiles

### 代码

#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;
}


# 题解：

#pragma GCC optimize(3)
#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)

typedef complex<double> pt, vec;
typedef pair<pt, pt> seg;

const double EPS = 1e-8;
int fcmp(double a, double b = 0.0) {
if (fabs(a - b) < EPS) return 0;
return a < b ? -1 : 1;
}

double operator * (pt a, pt b) {
return a.real() * b.imag() - a.imag() * b.real();
}

double operator , (pt a, pt b) {
return a.real() * b.real() + a.imag() * b.imag();
}

inline bool ptOnSeg(pt p, seg s){
vec v1 = s.first - p, v2 = s.second - p;
return fcmp((v1, v2)) <= 0 && fcmp(v1 * v2) == 0;
}

inline pt getIntersection(pt P, vec v, pt Q, vec w) {
return P + v * (w*(P-Q)/(v*w));
}

// -1 outside the polygon
// 0  on the border of the polygon
// 1  inside the polygon
int ptOnPoly(pt p, pt* poly, int n){
//  fprintf(stderr, "(%.7f, %.7f)\n", p);
int wn = 0;
for (int i = 0; i < n; i++){
if (ptOnSeg(p, {poly[i], poly[i+1]})) return 0;
int d1 = fcmp(poly[i].imag() - p.imag()),
d2 = fcmp(poly[i+1].imag() - p.imag()),
k = fcmp((poly[i+1] - poly[i])*(p - poly[i]));
if (k > 0 && d1 <= 0 && d2 > 0) wn++;
if (k < 0 && d2 <= 0 && d1 > 0) wn--;
}
return wn ? 1 : -1;
}

istream& operator >> (istream& lhs, pt& rhs){
double x, y;
lhs >> x >> y;
rhs = {x, y};
return lhs;
}

int n;
vector<pt> poly;
double ans = 0.0;

void attempt(pt a, pt b) {
vector<pt> points;
rep (i, n)
if (fcmp((b-a)*(poly[i]-a)) * fcmp((b-a)*(poly[i+1]-a)) <= 0) {
auto vec1 = b-a, vec2 = poly[i+1] - poly[i];
if (fcmp(vec1 * vec2) == 0) {
points.push_back(poly[i]);
points.push_back(poly[i+1]);
} else {
points.push_back(getIntersection(a, b-a, poly[i], poly[i+1]-poly[i]));
}
}
sort(range(points), [] (pt a, pt b) {
return make_pair(a.real(), a.imag()) < make_pair(b.real(), b.imag());
});
points.resize(unique(range(points), [] (pt a, pt b) {
return fcmp(a.real(), b.real()) == 0 && fcmp(a.imag(), b.imag()) == 0;
}) - points.begin());
double cur = 0.0;
assert(points.size() > 1);
for (int i = 1; i < points.size(); i++) {
if (ptOnPoly((points[i]+points[i-1]) / 2.0, poly.data(), n) >= 0) {
cur += abs(points[i] - points[i-1]);
} else {
cur = 0.0;
if (abs(points.back() - points[i]) <= ans) return;
}
ans = max(ans, cur);
}
}

int main() {
cin >> n; poly.resize(n);
rep (i, n) cin >> poly[i];
poly.push_back(poly[0]);
rep (i, n) {
rep (j, i) {
attempt(poly[i], poly[j]);
}
}
printf("%.8f\n", ans);
return 0;
}