# JZOJ – 3493 三角形

Time Limit : 1000ms
Memory Limit : 256MB

## Sample Input

5
0 0
1 1
1 -1
-1 -1
-1 1


## Sample Output

8


## 解题思路

$ans$ 减去 $\frac{cnt \times (cnt-1)}{2}$

## 代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>

using namespace std;
const int MAXN = 3000 + 10;

int x = 0;
int p = 1;
char ch = getchar();

while(ch < '0' || ch > '9'){
if(ch == '-')
p = 0;
ch = getchar();
}

while('0' <= ch && ch <= '9'){
x = x*10 + ch - '0';
ch = getchar();
}

return p ? x : (-x);
}

int n;
int x[MAXN], y[MAXN];
long long ans;

int main(){

freopen("triangle.in", "r", stdin);
freopen("triangle.out", "w", stdout);

for(register int i=1; i<=n; i++){
}

ans = ((long long)(n * (n-1))/2 * (n-2))/3;

for(register int i=1; i<=n; i++){

double tmp[MAXN]={};
int tmp2 = 0;
int cnt = 0;

for(register int j=i+1; j<=n; j++){
if(x[i] == x[j])
tmp2++;
else
tmp[cnt++] = (double)(y[j] - y[i]) / (double)(x[j] - x[i]);
}

ans -= tmp2 * (tmp2-1) /2;
tmp2 = 1;

sort(tmp, tmp+cnt);

for(register int j=1; j<cnt; j++){
if(tmp[j] == tmp[j-1])
tmp2++;
else
tmp2 = 1;

ans -= tmp2 - 1;
}
}

printf("%lld", ans);
return 0;
}