New Year and Castle Construction
题目描述
给定大小为 \(N\) 的点集 \(S\)。保证点集中的任意三点不共线，且不存在重复的点。
设 \(f(p)\) 表示满足如下条件的 \(S\) 的四元子集 \(T\) 的个数：
- \(T \subset S\ \land p \notin T\)
- \(T\) 中的元素能组成一个四边形，且满足 \(p\) 在四边形内部。
请你求出的 \(\sum_{p \in S} f(p)\) 的值。
\(N\le2.5\times10^3,-10^9\le x_i,y_i\le10^9\)
Solution
看数据范围感觉可以 \(\mathcal O(N^2)\) 的做，然后对于题目要统计的东西显然四边形内部的那个点最特殊，所以不妨就枚举最中间的这个点来统计答案。
考虑如何选这 \(4\) 个点。观察一下性质，如果直接找四个点感觉上没法做，因为这 \(4\) 个点相互约束，并且约束条件都不一致，所以考虑熔池一下，考虑什么样的 \(4\) 个点不会成为答案。
枚举最中间的点，然后从中心点向所有点作一条射线，那么如果一组点不会成为答案，那么这一组点的射线必定不会处在同一半平面上。考虑怎么计数，先将所有的射线极角排序，然后使用双指针即可找出所有不合法的射线区间。设不合法的区间大小为 \(k\)，那么这个区间将对答案造成 \(-\displaystyle\binom{k}{4}\) 的贡献。总共的答案数量即 \(n\times\displaystyle\binom{n-1}{4}\)。
时间复杂度为 \(\mathcal O(n^2\log n)\)。
首先计算 atan2 时需要开 long double，否则会被卡精度。其次，需要先计算出所有射线的极角后再进行排序，否则计算 atan2 的常数极大，极限数据需要跑 \(10\) 秒。
Code
struct Vec {
int x, y;
Vec(int x = 0, int y = 0) : x(x), y(y) {}
Vec operator + (const Vec& rhs) const {return Vec(x + rhs.x, y + rhs.y);}
Vec operator - (const Vec& rhs) const {return Vec(x - rhs.x, y - rhs.y);}
i64 operator * (const Vec& rhs) const {return 1ll * x * rhs.y - 1ll * rhs.x * y;}
};
int N, tot;
Vec poi[_N];
pair<long double, Vec> p[_N];
inline i64 sel3(int x) {return x < 3 ? 0 : 1ll * x * (x - 1) * (x - 2) / 6;}
inline i64 sel4(int x) {return x < 4 ? 0 : 1ll * x * (x - 1) * (x - 2) * (x - 3) / 24;}
i64 solve(int id) {
tot = 0; Vec cp = poi[id];
auto getAng = [](const Vec& i, const Vec& j)->long double {
return atan2l(i.x - j.x, i.y - j.y);
};
For(i, 1, N) if (i != id) p[++tot] = {getAng(poi[i], cp), poi[i]};
sort(p + 1, p + tot + 1, [&cp](const auto& i, const auto& j) {
return i.first > j.first;
});
i64 res = sel4(tot);
auto nxt = [&](int x)->int {return x == tot ? 1 : x + 1;};
for (int i = 1, j = 2; i <= tot; ++i) {
while ((cp - p[i].second) * (p[j].second - cp) < 0) j = nxt(j);
res -= j > i ? sel3(j - i - 1) : sel3(j + tot - i - 1);
}
return res;
}
signed main() {
cin.tie(0)->sync_with_stdio(0);
cin >> N;
For(i, 1, N) cin >> poi[i].x >> poi[i].y;
i64 ans = 0;
For(i, 1, N) ans += solve(i);
cout << ans << '\n';
}