结论:如果两个三角形不相交,那么一定存在两条内公切线。
于是可以考虑枚举这条内公切线的端点 \(x, y\)。
那么一个三角形的两个端点就会在 \(x\to y\) 这条线的同一侧,另外一个三角形的两个端点会在这条线的另一侧。
同时这条线的一侧与其配对的端点可能是 \(x\) 也可能是 \(y\)。
所以令在 \(x\to y\) 这条线下面的点的数量为 \(c\),方案数为 \(2\binom{c}{2}\binom{n - 2 - c}{2}\)。
那么可以先枚举 \(x\)。
然后对于每个点按照 \(x\) 极角排序。
再枚举 \(y\),可以用双指针求出在 \(x\to y\) 一侧的点的数量然后计数。
考虑到一对三角形会被 \(2\) 条内切线算到,而因为还定了向,所以会被 \(4\) 条算上。
于是最后答案需除 \(4\)。
时间复杂度 \(O(n^2\log n)\)。
#include<bits/stdc++.h>
#define C2(x) ((x) * ((x) - 1) / 2)
const int maxn = 2e3 + 10;
const double pi = acos(-1);
int X[maxn], Y[maxn];
double a[maxn * 2];
int main() {
int n; scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d%d", &X[i], &Y[i]);
long long ans = 0;
for (int i = 1; i <= n; i++) {
int m = 0;
for (int j = 1; j <= n; j++) j != i && (a[++m] = atan2(Y[j] - Y[i], X[j] - X[i]), 1);
std::sort(a + 1, a + m + 1);
for (int j = 1; j <= m; j++) a[m + j] = a[j] + pi * 2.0;
for (int l = 1, r = 1; l <= m; l++) {
while (a[r] < a[l] + pi) r++;
int c1 = r - l - 1, c2 = n - 2 - c1;
ans += 2ll * C2(c1) * C2(c2);
}
}
printf("%lld\n", ans / 4);
return 0;
}
标签:这条线,int,Codeforces,枚举,maxn,端点,Disjoint,三角形,Triangles
From: https://www.cnblogs.com/rizynvu/p/18031672