题目大意
平面上有n个点，求出用这些点可以构成的三角形数。
题目分析
显然能够构成三角形需满足三点不共线。
枚举点$i$，枚举尚未枚举过的点$j$，计算出直线$i\rightarrow j$直线的斜率。
用双指针扫描一下跳过斜率相同的，然后计算个数即可。
代码
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
| #include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
typedef long long LL;
inline const LL Get_Int() {
LL num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
struct Point {
double x,y;
} p[3005];
LL n,ans=0;
double k[3005];
double Cal(Point a,Point b) {
if(fabs(a.x-b.x)<=1e-11)return 1e17;
return (b.y-a.y)/(b.x-a.x);
}
int main() {
n=Get_Int();
for(int i=1; i<=n; i++) {
p[i].x=Get_Int();
p[i].y=Get_Int();
}
for(int i=n; i>=3; i--) {
int cnt=0;
for(int j=1; j<i; j++)k[++cnt]=Cal(p[i],p[j]);
sort(k+1,k+cnt+1);
int lpos=1,rpos=1;
while(lpos<=cnt) {
while(rpos<=cnt&&fabs(k[rpos]-k[lpos])<=1e-11)rpos++;
ans+=(i-(rpos-lpos+1))*(rpos-lpos);
lpos=rpos;
}
}
printf("%lld\n",ans/2);
return 0;
}
|
