胡闹 统计三角形

题目大意

给你平面上$n\le3000$个点,每个点有一个颜色$c_i\in[0,2]$。

定义一个三角形是好的,当且仅当这个三角形的三个定点颜色不同。

定义一对三角形是好的,当且仅当这两个三角形是好的其这两个三角形没有交集。

为了避免歧义,保证点的坐标互不相同。

统计好的三角形对有多少。

解析

首先,两个三角形没有交集的的充要条件是这两个三角形之间存在两条内公切线。

那么我们就可以枚举内公切线。

这条直线会把平面分成两个部分,然后有贡献的点对一定一个在这条直线左边,一个在这条直线右边。

那我们可以先枚举一个点,然后把其他的点做极角排序。极角排序用向量比较麻烦,那就直接三角函数吧。

按照这样的顺序枚举两个点来枚举内公切线,就可以保证每次都只会把一个点从一边丢到另一边去。

统计的时候大力讨论一下颜色就可以了。

Notice

值得注意的是,如果管坐标大小直接随便搞,答案会是真正的答案的$4$倍,要记得把这个东西搞掉。

Code

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
#define REP(i, s, e) for (int i = s; i <= e; i++)

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
const int maxn = 3000 + 10;
const double pi = acos(-1), inf = 1e20;

int n;long long ans;
int cnt[2][3];
//cnt[0/1][x] 分割线左右的cnt
bool app[maxn];
//被搞过去几次

struct point
{
int x, y, c, id;
double k;

bool operator < (point B) const {return k < B.k;}//极角排序
}P[maxn], p[maxn], O;

int main()
{
#ifndef ONLINE_JUDGE
freopen("B.in", "r", stdin);
freopen("B.out", "w", stdout);
#endif
cin >> n;
REP(i, 1, n) scanf("%d%d%d", &P[i].x, &P[i].y, &P[i].c), P[i].id = i;

long long tmp;
REP(i, 1, n)
{
O = P[i];
int k = O.c;
copy(P + 1, P + 1 + n, p + 1);
int cur(0);
REP(j, 1, n)
if (i ^ p[j].id)
{
p[++cur]=p[j];
p[cur].k = atan2(p[cur].y - O.y, p[cur].x - O.x);
if (p[cur].k <= 0) p[cur].k += pi;
}
sort(p + 1, p + n);
memset(cnt, 0, sizeof(cnt));
memset(app, 0, sizeof(app));
REP(j, 1, cur)
if (p[j].y < O.y || p[j].y == O.y && p[j].x > O.x) ++cnt[0][p[j].c];//一开始下面
else ++cnt[1][p[j].c], app[j] = 1;
REP(j, 1, cur)
{
--cnt[app[j]][p[j].c];
tmp = 1ll * (k ? cnt[0][0] : 1) * (p[j].c ? cnt[1][0] : 1) * ((k ^ 1) ? cnt[0][1] : 1) * ((p[j].c ^ 1) ? cnt[1][1] : 1) * ((k ^ 2) ? cnt[0][2] : 1) * ((p[j].c ^ 2) ? cnt[1][2] : 1);//大力统计颜色
ans += tmp;
tmp = 1ll * (k ? cnt[1][0] : 1) * (p[j].c ? cnt[0][0] : 1) * ((k ^ 1) ? cnt[1][1] : 1) * ((p[j].c ^ 1) ? cnt[0][1] : 1) * ((k ^ 2) ? cnt[1][2] : 1) * ((p[j].c ^ 2) ? cnt[0][2] : 1);
ans += tmp;
++cnt[app[j] ^= 1][p[j].c];
}
}
cout << ans / 4 << endl;
return 0;
}

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×