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.
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
#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