2023 ICPC 济南站 M 题题解

2023 ICPC 亚洲区域赛济南站 M 题

首先求出 S 的凸包作为 P。首先 P 本身就是可能的 Q，然后要统计所有满足 |Q| = |P| +1 的 Q。

不难发现 Q 仍然要包含 P 的所有点，只能在 S 中再选一个不是 P 的顶点的点作为 Q 的顶点。

枚举新加的点 w，只能从 P 上选两个相邻的点 u 和 v，切断 u −v 然后连接 u − w 和 v − w。

这要求 w,u,v 构成的三角形区域内没有其他 S 内的点。问题转化为找出所有合法的 (w,u,v)。

枚举 S 中不是 P 的顶点的点 w 之后将其他所有点以 w 为极点进行极角排序，当 P 上相邻两个点 u 和 v 具有相邻的极角序时，这组 (u,v,w) 是合法的。

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

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using db = double;
#define dbg(x) cerr << #x << " = " << (x) << endl;
#define vdbg(a) cout << #a << " = "; for (auto x : a) cout << x << " "; cout << endl;


struct Point { db x, y; int id; };
using Vec = Point;
Vec operator-(Vec a, Vec b) {
    return {a.x - b.x, a.y - b.y};
}
bool operator==(Vec a, Vec b) {
    return a.x == b.x && a.y == b.y;
}
db cross(Vec u, Vec v) {
    return u.x * v.y - u.y * v.x;
}
vector<Point> Andrew(vector<Point> p) {
    sort(p.begin(), p.end(), [&](Point a, Point b) {
        return a.x == b.x ? a.y < b.y : a.x < b.x;
    });
    p.erase(unique(p.begin(), p.end()), p.end());
    int n = p.size();

    vector<Point> hi, lo;
    for (int i = 0; i < n; ++i) {
        while (hi.size() > 1 && cross(hi.back() - hi[hi.size() - 2], p[i] - hi.back()) >= 0) hi.pop_back();
        while (lo.size() > 1 && cross(lo.back() - lo[lo.size() - 2], p[i] - lo.back()) <= 0) lo.pop_back();
        hi.push_back(p[i]);
        lo.push_back(p[i]);
    }
    vector<Point> hull;
    for (int i = 0; i < lo.size(); ++i) hull.push_back(lo[i]);
    for (int i = hi.size() - 2; i > 0; --i) hull.push_back(hi[i]);
    return hull;
}

db theta(Vec u) {
    return atan2(u.y, u.x);
}
// precompute polar angle to reduce constant
void psort2(vector<Point>& p, Point c) {
    int n = p.size();
    vector<pair<db, int>> ang(n);
    for (int i = 0; i < n; ++i) {
        ang[i] = {theta(p[i] - c), i};
    }
    sort(ang.begin(), ang.end());
    vector<Point> res(n);
    for (int i = 0; i < n; ++i) {
        res[i] = p[ang[i].second];
    }
    p = move(res);
}

void solve() {  
    int n; cin >> n;
    vector<Point> p(n);
    for (int i = 0; i < n; ++i) {
        db x, y; cin >> x >> y;
        p[i] = {x, y, i};
    }
    vector<Point> t = Andrew(p);
    vector<bool> vis(n);
    for (auto [x, y, id] : t) vis[id] = 1;
    // vdbg(vis);
    int ans = 0;
    for (int i = 0; i < n; ++i) {
        if (vis[i]) continue;
        vector<Point> q;
        for (int j = 0; j < n; ++j) {
            if (j == i) continue;
            q.push_back(p[j]);
        }
        psort2(q, p[i]);
        for (int j = 0; j < n - 1; ++j) {
            int nj = (j + 1) % (n - 1);
            if (vis[q[j].id] && vis[q[nj].id]) ans++;
        }
    }
    cout << ans + 1 << "\n";
}   


signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(10);
    
    int T = 1;
    // cin >> T;  
    while (T--) solve();
    return 0;
}