NOIP 模拟赛 T1，小清新几何题。
要让选出的点组成的多边形面积最大，就要让正多边形的面积减去选出的点组成的多边形面积最小。而这个面积差可以表示成 \(2n\) 个三角形的面积，即 \(\sum\limits_{i = 0}^{2n - 1} S_{\triangle A_i A_{(i + 1) \bmod n} B_{(i + 1) \bmod n}}\)。
众所周知 \(S_{\triangle} = \frac{1}{2} ab \sin \theta\)，而在本题中 \(\theta\) 恒等于正 \(2n\) 多边形的内角，因此可以约去。如果令给出的排列为 \(p\)，要求的排列为 \(q\)，相当于最小化 \(\sum\limits_{i = 0}^{n - 1} (n - p_i) q_i + (n - q_i) p_{(i + 1) \bmod n}\)。化简后相当于最大化 \(\sum\limits_{i = 0}^{n - 1} q_i (p_i + p_{(i + 1) \bmod n})\)。
令 \(c_i = p_i + p_{(i + 1) \bmod n}\)，式子变成 \(\sum\limits_{i = 0}^{n - 1} q_i c_i\)。显然小的和小的配对，大的和大的配对，因此 \(q_i\) 即为 \(c_i\) 的排名。排序求一下即可。
code
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 200100;
int n, a[maxn], b[maxn], c[maxn], d[maxn];
void solve() {
scanf("%d", &n);
for (int i = 0; i < n; ++i) {
scanf("%d", &a[i]);
b[i] = i;
}
for (int i = 0; i < n; ++i) {
d[i] = a[i] + a[(i + 1) % n];
}
sort(b, b + n, [&](const int &x, const int &y) {
return d[x] < d[y] || (d[x] == d[y] && x < y);
});
for (int i = 0; i < n; ++i) {
c[b[i]] = i;
}
for (int i = 0; i < n; ++i) {
printf("%d ", c[i]);
}
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}