Loj 2882 两个人的星座

Posted on | Edited on | Views:

极角排序.

两个三角形如果相离,则一定可以用公切线分开.

枚举两个点的连线作为公切线,统计两个半平面中各类颜色点的数目,时间复杂度 $O(n^3)$ .

优化一下,先枚举一个点作为原点,对其他点极角排序.

再枚举另一个点,用前缀和询问两个半平面中各类颜色点的数目.

由于两个相离的三角形通过顶点相连可以产生 $4$ 根公切线,所以最后还需要将答案除掉 $4$ .

时间复杂度 $O(n^2\log n)$ .

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
//%std
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out = 0, fh = 1;
	char jp = getchar();
	while ((jp > '9' || jp < '0') && jp != '-')
		jp = getchar();
	if (jp == '-')
		fh = -1, jp = getchar();
	while (jp >= '0' && jp <= '9')
		out = out * 10 + jp - '0', jp = getchar();
	return out * fh;
}
const int N = 3e3 + 10;
int sgn(int x)
{
	return x >= 0;
}
struct v2
{
	int x, y, col;
	v2(int x = 0, int y = 0, int col = 0) : x(x), y(y), col(col) {}
	v2 operator + (const v2 &rhs) const
	{
		return v2(x + rhs.x, y + rhs.y, col);
	}
	v2 operator - (const v2 &rhs) const
	{
		return v2(x - rhs.x, y - rhs.y, col);
	}
	ll operator * (const v2 &rhs) const
	{
		return 1LL * x * rhs.y - 1LL * y * rhs.x;
	}
	friend bool operator < (v2 A, v2 B)
	{
		if (sgn(A.y) != sgn(B.y))
			return sgn(A.y) > sgn(B.y);
		return A * B > 0;
	}
} p[N], a[N];
int n, sum[N][3], pos[N], t[2][3];
int query(int l, int r, int col)
{
	if (l > r)
		return 0;
	return sum[r][col] - sum[l - 1][col];
}
ll calc()
{
	for (int i = 2; i <= n; ++i)
		a[i - 1] = p[i] - p[1];
	sort(a + 1, a + n);
	for (int i = 1; i < n; ++i)
	{
		for (int j = 0; j < 3; ++j)
			sum[i][j] = sum[i - 1][j];
		++sum[i][a[i].col];
	}
	ll s = 0;
	for (int i = 1; i < n; ++i)
	{
		v2 iv = v2(0, 0, 0) - a[i];
		int l = i, r = lower_bound(a + 1, a + n, iv) - a;
		memset(t, 0, sizeof t);
		for (int j = 0; j < 3; ++j)
		{
			t[0][j] += query(r, n - 1, j);
			t[0][j] += query(1, l - 1, j);
			t[1][j] += query(l + 1, r - 1, j);
		}
		int c = p[1].col, d = a[i].col;
		for (int id = 0; id < 2; ++id)
		{
			ll prod = 1;
			for (int j = 0; j < 3; ++j)
			{
				if (c != j)
					prod *= t[id][j];
				if (d != j)
					prod *= t[id ^ 1][j];
			}
			s += prod;
		}
	}
	return s;
}
int main()
{
	n = read();
	for (int i = 1; i <= n; ++i)
	{
		p[i].x = read(), p[i].y = read();
		p[i].col = read();
	}
	ll ans = 0;
	for (int i = 1; i <= n; ++i)
	{
		swap(p[1], p[i]);
		ans += calc();
		swap(p[1], p[i]);
	}	
	ans /= 2;
	printf("%lld\n", ans);
	return 0;
}