Editorial for Convex Hull bản 1


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: Yunan

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll mod = 1e9 + 7;

int sign(int a) {
    return !a ? 0 : (a > 0 ? 1 : - 1);
}

struct point {
    int x, y;

    point() {}
    point(int _x, int _y) {
        x = _x, y = _y;
    }

    bool operator < (point p) {
        return x != p.x ? x < p.x : y < p.y;
    }

    point operator - (point p) {
        return point(x - p.x, y - p.y);
    }

    int cross(point p) {
        return x * p.y - y * p.x;
    }

    // Xác định chiều của 3 điểm (*this, pa, pb)
    int ccw(point pa, point pb) {
        return sign((pa - *this).cross(pb - *this));
    }

    // Diện tích tam giác tạo bởi 3 điểm (*this, pa, pb)
    int area(point pa, point pb) {
        return abs((pa - *this).cross(pb - *this));
    }

    // Kiểm tra một điểm nằm trong đa giác
    bool inSimplePolygon(vector <point> &vecP) {
        int n = vecP.size(), cnt = 0;
        for (int i = 0; i < n; ++i) {
            int iNext = (i + 1) % n;
            point pa = vecP[i], pb = vecP[iNext];
            if (pa.y > pb.y) {
                swap(pa, pb);
            }
            if (pa.y <= y && y < pb.y && ccw(pa, pb) < 0) {
                cnt++;
            }
        }
        return cnt % 2;
    }
};

int n;
vector <point> vecP;

void Task() {
    ios_base :: sync_with_stdio(false); cin.tie(0); cout.tie(0);
    if (fopen("test.inp", "r")) {
        freopen("test.inp", "r", stdin);
        freopen("test.out", "w", stdout);
    }
}

void Solve() {
    cin >> n;
    vecP.resize(n + 1);
    for (int i = 1; i <= n; ++i) {
        cin >> vecP[i].x >> vecP[i].y;
    }

    // Sắp xếp các điểm theo thứ tự tăng dần hoành độ x
    sort(vecP.begin() + 1, vecP.end());

    // Tính các giá trị parity[a][b][c] và cnt[a][b][c]
    vector <vector <vector <int>>> vecParity, vecCnt;
    vecParity.assign(n + 1, vector <vector <int>> (n + 1, vector <int> (n + 1, 0)));
    vecCnt.assign(n + 1, vector <vector <int>> (n + 1, vector <int> (n + 1, 0)));
    for (int i = 1; i + 2 <= n; ++i) {
        for (int j = i + 1; j + 1 <= n; ++j) {
            for (int k = j + 1; k <= n; ++k) {
                vecParity[i][j][k] = vecP[i].area(vecP[j], vecP[k]) % 2;
                vector <point> vecP1 = {vecP[i], vecP[j], vecP[k]};
                for (int l = 1; l <= n; ++l) {
                    if (l == i || l == j || l == k) {
                        continue;
                    }
                    if (vecP[l].inSimplePolygon(vecP1)) {
                        vecCnt[i][j][k]++;
                    }
                }
            }
        }
    }

    // Lũy thừa của 2
    vector <ll> vecPow2(n + 1);
    vecPow2[0] = 1;
    for (int i = 1; i <= n; ++i) {
        vecPow2[i] = (vecPow2[i - 1] * 2LL) % mod;
    }

    // Tính kết quả bài toán
    ll ans = 0;
    for (int left = 1; left <= n; ++left) {
        vector <vector <vector <vector <ll>>>> vecDP;
        vecDP.assign(2, vector <vector <vector <ll>>> (n + 1, vector <vector <ll>> (n + 1, vector <ll> (2, 0))));

        // Cơ sở QHĐ:
        for (int i = left + 1; i <= n; ++i) {
            vecDP[0][left][i][0] = vecDP[1][left][i][0] = 1;
        }

        // Áp dụng công thức QHĐ để tính dp[z][i][j][k]
        for (int j = left + 1; j <= n; ++j) {
            for (int k = 0; k <= 1; ++k) {
                for (int i = left; i < j; ++i) {
                    for (int l = j + 1; l <= n; ++l) {
                        int parity = k ^ vecParity[left][j][l];
                        if (vecP[i].ccw(vecP[j], vecP[l]) < 0) {
                            // 3 điểm Pi, Pj, Pl theo chiều kim đồng hồ, tương ứng với Upper
                            vecDP[0][j][l][parity] = (vecDP[0][j][l][parity] + (vecDP[0][i][j][k] * vecPow2[vecCnt[left][j][l]]) % mod) % mod;
                        } else {
                            // 3 điểm Pi, Pj, Pl ngược chiều kim đồng hồ, tương ứng với Lower
                            vecDP[1][j][l][parity] = (vecDP[1][j][l][parity] + (vecDP[1][i][j][k] * vecPow2[vecCnt[left][j][l]]) % mod) % mod;
                        }
                    }
                }
            }
        }

        // Cập nhật kết quả
        for (int j = left + 1; j <= n; ++j) {
            for (int k = 0; k <= 1; ++k) {
                ll upper = 0, lower = 0;
                for (int i = left; i < j; ++i) {
                    upper = (upper + vecDP[0][i][j][k]) % mod;
                    lower = (lower + vecDP[1][i][j][k]) % mod;
                }
                ans = (ans + (upper * lower) % mod) % mod;
            }
        }
    }

    // Lưu ý phải trừ đi số cách chọn tập S gồm 2 điểm
    ans = (ans - n * (n - 1) / 2 + mod) % mod;
    cout << ans;
}

int main() {
    Task();
    Solve();
}

Comments