HDU 5784 How Many Triangles【极角排序】

题目链接:

http://acm.hdu.edu.cn/showproblem.php?pid=5784

题意:

给定二维平面$n$个不相同的点,求组成锐角三角形个数。
数据范围:$3 \le n \le 2000$

分析:

直接求锐角三角形个数不好求,正难则反,我们考虑求钝角三角形、直角三角形和三点共线情况的个数。
考虑直接钝角三角形内仅有一个直角和钝角,那么$锐角三角形个数=C(n,3) - 钝角个数 - 直角个数 - 三点共线个数$
枚举点,求出其他点与该点构成的向量,做极角排序。
根据点积大于0,叉积等于0我们可以求出三点共线的个数。
接下来对于每个向量,考虑其与左边所有向量(叉积小于0)中夹角为直角和钝角的个数,为方便计算,此时我们先求出所有向量个数,再减去左边锐角(点积大于0)个数。
因为是个环,所以在处理过程中还要将向量拷贝一份。

代码:

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
/*************************************************************************
> File Name: 5784.cpp
> Author: jiangyuzhu
> Mail: 834138558@qq.com
> Created Time: 2016/10/4 14:28:41
************************************************************************/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#include<set>
#include<map>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn = 1e4 + 5;
struct P{
ll x, y;
P() {}
P(ll x, ll y) : x(x), y(y){}
P operator + (P p){
return P(x + p.x, y + p.y);
}
P operator -(P p){
return P(x -p.x, y - p.y);
}
ll dot(P p){
return x * p.x + y *p.y;
}
ll det(P p){
return x * p.y - y * p.x;
}
bool operator < (const P& a) const{
if(y * a.y <= 0){
if(y > 0 || a.y > 0) return y < a.y;
if(y == 0 && a.y == 0) return x < a.x;
}
return x * a.y - y * a.x > 0;
}
}p[maxn], q[maxn << 1];
int main (void)
{
int n;
while(~scanf("%d", &n)){
for(int i = 0; i < n; ++i){
scanf("%lld%lld", &p[i].x, &p[i].y);
}
ll line = 0;
ll ans = n * 1ll * (n - 1) * (n - 2) / 6;
for(int i = 0; i < n; ++i){
int tot = 0;
for(int j = 0; j < n; ++j){
if(i == j) continue;
q[tot++] = p[j] - p[i];
}
int tmp = 0;
sort(q, q + tot);
for(int j = 0; j < tot; ++j) q[tot + j] = q[j];
for(int j = 0; j < tot - 1; ++j){
if(q[j].det(q[j + 1]) == 0 && q[j].dot(q[j + 1]) > 0) tmp++;//三点共线
else tmp = 0;
line += tmp;
}
int cnt1 = 0, cnt2 = 0;
for(int j = 0; j < tot; ++j){
while(cnt1 <= j || (cnt1 - tot < j && q[cnt1].det(q[j]) < 0 && q[j].dot(q[cnt1]) > 0)) cnt1++;//左边锐角个数
while(cnt2 <= j || (cnt2 - tot < j && q[cnt2].det(q[j]) < 0)) cnt2++;//左边角个数
ans -= cnt2 - cnt1;
}
}
ans -= line / 2;
printf("%lld\n", ans);
}
return 0;
}
文章目录
  1. 1. 题目链接:
  2. 2. 题意:
  3. 3. 分析:
  4. 4. 代码: