题解 P9702【[GDCPC2023] Computational Geometry】

· · 题解

这题一看就不是计算几何，考虑区间 DP。

设凸多边形的 n 个顶点依次为 P_1,P_2,\cdots,P_n。

设 f_{i,j} 在 i < j 时表示 P_i,P_{i+1},\cdots,P_{j-1},P_j 组成的多边形的直径的平方，在 i > j 时表示 P_i,P_{i+1},\cdots,P_n,P_1,\cdots,P_{j-1},P_j 组成的多边形的直径的平方。容易得到转移方程：

f_{i,j}=\max\{f_{i+1,j},f_{i,j-1},dis^2(P_i,P_j)\}

其中下标均为模 n 意义下。

答案即为每一对能将多边形分为两个面积为正的部分的点 (P_i,P_j) 中，f_{i,j}+f_{j,i} 的最小值。其中，(P_i,P_j) 能将多边形分为两个面积为正的部分，当且仅当 P_{i-1},P_i,P_j 不共线，且 P_i,P_{i+1},P_j 不共线，使用向量叉积计算即可。

时间复杂度 O(n^2)。

// Problem: T368391 [GDCPC2023] M-Computational Geometry
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/T368391?contestId=135929
// Memory Limit: 1 MB
// Time Limit: 4000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

//By: OIer rui_er
#include <bits/stdc++.h>
#define rep(x, y, z) for(ll x = (y); x <= (z); ++x)
#define per(x, y, z) for(ll x = (y); x >= (z); --x)
#define debug(format...) fprintf(stderr, format)
#define fileIO(s) do {freopen(s".in", "r", stdin); freopen(s".out", "w", stdout);} while(false)
#define endl '\n'
using namespace std;
typedef long long ll;

mt19937 rnd(std::chrono::duration_cast<std::chrono::nanoseconds>(std::chrono::system_clock::now().time_since_epoch()).count());
ll randint(ll L, ll R) {
    uniform_int_distribution<ll> dist(L, R);
    return dist(rnd);
}

template<typename T> void chkmin(T& x, T y) {if(x > y) x = y;}
template<typename T> void chkmax(T& x, T y) {if(x < y) x = y;}

const ll N = 5e3 + 5;

ll T, n, x[N], y[N], diam[N][N];

inline ll sq(ll x) {return x * x;}
inline bool line(ll i, ll j, ll k) {
    ll v1x = x[i] - x[j], v1y = y[i] - y[j];
    ll v2x = x[i] - x[k], v2y = y[i] - y[k];
    return v1x * v2y - v2x * v1y == 0;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    for(cin >> T; T; --T) {
        cin >> n;
        rep(i, 0, n - 1) cin >> x[i] >> y[i];
        auto inc = [&](ll x) {return (x + 1) % n;};
        auto dec = [&](ll x) {return (x - 1 + n) % n;};
        rep(dt, 1, n - 1) {
            rep(L, 0, n - 1) {
                ll R = (L + dt) % n;
                diam[L][R] = max({diam[inc(L)][R], diam[L][dec(R)], sq(x[L] - x[R]) + sq(y[L] - y[R])});
            }
        }
        ll ans = numeric_limits<ll>::max();
        rep(i, 0, n - 1) {
            rep(j, 0, n - 1) {
                if(!line(dec(i), i, j) && !line(i, inc(i), j)) {
                    chkmin(ans, diam[i][j] + diam[j][i]);
                }
            }
        }
        cout << ans << endl;
    }
    return 0;
}