Codeforces Round #308(Div.2)--D(사비테마)

D. Vanya and Triangles
time limit per test
4 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output
Vanya got bored and he painted n distinct points on the plane. After that he connected all the points pairwise and saw that as a result many triangles were formed with vertices in the painted points. He asks you to count the number of the formed triangles with the non-zero area.
Input
The first line contains integer n (1 ≤ n ≤ 2000) — the number of the points painted on the plane.
Next n lines contain two integers each xi, yi ( - 100 ≤ xi, yi ≤ 100) — the coordinates of the i-th point. It is guaranteed that no two given points coincide.
Output
In the first line print an integer — the number of triangles with the non-zero area among the painted points.
Sample test(s)
input

4
0 0
1 1
2 0
2 2

output

3

input

3
0 0
1 1
2 0

output

1

input

1
1 1

output

0

Note
Note to the first sample test. There are 3 triangles formed: (0, 0) - (1, 1) - (2, 0); (0, 0) - (2, 2) - (2, 0); (1, 1) - (2, 2) - (2, 0).
Note to the second sample test. There is 1 triangle formed: (0, 0) - (1, 1) - (2, 0).
Note to the third sample test. A single point doesn't form a single triangle.
제목: n개의 점의 좌표를 주고 모든 두 점을 연결시켜 몇 개의 삼각형을 구성할 수 있는지 구한다.
처음부터 검색을 하고 싶었어요.
방법 1:
만약 x(x>2)개의 점이 일선으로 연결된 상황이 없다면 답은 C(n,3)이다.만약 x(x>2)개의 점이 일선으로 연결된 상황이 있다면 이 점들은 구성된 삼각형의 개수가 C(n,3)보다 적은 원인이다(다른 점은 영향을 주지 않는다).그래서 이 점들이 삼각형에 영향을 미치는 개수만 빼면 답이다.반면 이들 연일선점은 삼각형을 이루지 않지만, C(x, 3)를 구성할 수 있어 C(x, 3)개를 줄였다.계산이 편리하기 때문에 한 점을 매거하는 동시에 다른 점을 매거하여 이 두 점으로 구성된 사율을 기록한 다음에 정렬하여cnt개의 사율이 같다는 것을 찾아낼 수 있다.이 cnt의 경사율이 같다는 것은 그 점을 매거할 때 cnt+1개의 점이 일선으로 연결되어 있음을 나타낸다. 그러면 감소된 삼각형의 개수는 C(cnt, 2)이다.시간 복잡도는 O (n*n*logn)
방법2:
다른 사람이 쓴 것을 보고 이렇게 할 수 있다니 =, 나는 왜 ==#을 생각하지 못했을까
직접 폭력으로 세 가지를 매거한 후에 그 면적을 계산하고 0이 아니면 삼각형을 구성할 수 있다. 그렇지 않으면 안 된다.시간의 복잡도는 O(n^3)이다.cf에서 10^9의 복잡도 1sec를 모두 통과할 수 있을 것 같습니다.