乱做的，没想到就过了
思路就是枚举一条分割线，把$n$个点分为两部分（需要保证两部分点数相同或相差为1）
两部分内部不连，但互相连边（且连边不交叉），就大概连成一个锯齿的形状
实现的时候可以选择这样的方式，每次分割线都为$x=mid$（$n$为偶数则为所有$x$的中位数，$n$为奇数则为中位数加减一个极小值），但每次需要将所有点旋转一个角度
保证连边不相交可以把两个点集分别按照$y$排序，然后$x=mid$左右的点每次都向对面点集$y$值比自己大的点中选择$y$值最小的来连边就行了
代码实现似乎不够精细，好像转过的总角度只要$\pi$就行了？反正我也只当这是个骗分方法
时间复杂度$\Theta (knlogn)$,$k$为旋转的总次数
#include <bits/stdc++.h> using namespace std; const double eps = 1e-10; const double an = 1.0 / 180.0 * acos(-1.0); const double si = sin(an), co = cos(an); int n; double mid; struct point { double x, y; int id; } a[5010], b[5010]; inline bool cmp1(const point &g, const point &h) { return g.x < h.x; } inline bool cmp2(const point &g, const point &h) { return (g.x <= mid) == (h.x <= mid) ? g.y < h.y : g.x < h.x; } void rotate() { for (int i = 1; i <= n; i++) { double x = a[i].x, y = a[i].y; a[i].x = x * co - y * si; a[i].y = y * co + x * si; } } inline bool pd(int i, int j, int k) { return (b[i].x - b[j].x) * (b[k].x - b[j].x) + (b[i].y - b[j].y) * (b[k].y - b[j].y) > 0; } bool check(int opt) { int p = 1, q; if (n & 1) q = (opt ? n / 2 + 1 : n / 2 + 2); else q = n / 2 + 1; if (!opt) { for (int i = 2; i < n; i++) if (i & 1) { if (!pd(a[q].id, a[p].id, a[q + 1].id)) return false; q++; } else { if (!pd(a[p].id, a[q].id, a[p + 1].id)) return false; p++; } } else { for (int i = 2; i < n; i++) if (i & 1) { if (!pd(a[p].id, a[q].id, a[p + 1].id)) return false; p++; } else { if (!pd(a[q].id, a[p].id, a[q + 1].id)) return false; q++; } } return true; } void print(int opt) { /*printf("%d\n", opt); for (int i = 1; i <= n; i++) printf("%d ", a[i].id); putchar(‘\n‘);*/ int p = 1, q; if (n & 1) q = (opt ? n / 2 + 1 : n / 2 + 2); else q = n / 2 + 1; if (!opt) { printf("%d ", a[p].id); for (int i = 2; i <= n; i++) if (i & 1) printf("%d ", a[p].id), q++; else printf("%d ", a[q].id), p++; //printf("%d ", a[(n & 1) ? p : q].id); } else { printf("%d ", a[q].id); for (int i = 2; i <= n; i++) if (i & 1) printf("%d ", a[q].id), p++; else printf("%d ", a[p].id), q++; //printf("%d ", a[(n & 1) ? q : p].id); } exit(0); } int main() { scanf("%d", &n); for (int i = 1; i <= n; i++) scanf("%lf%lf", &a[i].x, &a[i].y), a[i].id = i, b[i] = a[i]; for (int i = 1; i <= 180; i++) { rotate(); sort(a + 1, a + n + 1, cmp1); if (n & 1) { mid = a[n / 2 + 1].x + eps; sort(a + 1, a + n + 1, cmp2); if (check(0)) print(0); mid = a[n / 2 + 1].x - eps; if (check(1)) print(1); } else { mid = (a[n / 2].x + a[n / 2 + 1].x) / 2; sort(a + 1, a + n + 1, cmp2); if (check(0)) print(0); if (check(1)) print(1); } } puts("-1"); return 0; }
Codeforces1478F - Nezzar and Nice Beatmap
原文：https://www.cnblogs.com/Urushibara-Ruka/p/14344356.html