102242: [AtCoder]ABC224 C - Triangle?

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Score : $300$ points

Problem Statement

In the $xy$-plane, we have $N$ points numbered $1$ through $N$.
Point $i$ is at the coordinates $(X_i,Y_i)$. Any two different points are at different positions.
Find the number of ways to choose three of these $N$ points so that connecting the chosen points with segments results in a triangle with a positive area.

Constraints

  • All values in input are integers.
  • $3 \le N \le 300$
  • $-10^9 \le X_i,Y_i \le 10^9$
  • $(X_i,Y_i) \neq (X_j,Y_j)$ if $i \neq j$.

Input

Input is given from Standard Input in the following format:

$N$
$X_1$ $Y_1$
$X_2$ $Y_2$
$\dots$
$X_N$ $Y_N$

Output

Print the answer as an integer.


Sample Input 1

4
0 1
1 3
1 1
-1 -1

Sample Output 1

3

The figure below illustrates the points.

There are three ways to choose points that form a triangle: $\{1,2,3\},\{1,3,4\},\{2,3,4\}$.


Sample Input 2

20
224 433
987654321 987654321
2 0
6 4
314159265 358979323
0 0
-123456789 123456789
-1000000000 1000000000
124 233
9 -6
-4 0
9 5
-7 3
333333333 -333333333
-9 -1
7 -10
-1 5
324 633
1000000000 -1000000000
20 0

Sample Output 2

1124

Input

题意翻译

给出 $n$ 个点,第 $i$ 个点在平面直角坐标系上的坐标为 $(x_i,y_i)$ 。现在从其中选出三点组成三角形,若三角形的面积为正数,问有多少个不同的符合要求的三角形?

Output

得分:300分

问题描述

在$xy$平面上,我们有$N$个编号为$1$到$N$的点。点$i$在坐标$(X_i,Y_i)$。任何两个不同的点都在不同的位置。

找出从这$N$个点中选择三个点的方式,使得用线段连接所选点得到一个面积为正的三角形。

约束条件

  • 输入中的所有值都是整数。
  • $3 \le N \le 300$
  • $-10^9 \le X_i,Y_i \le 10^9$
  • 如果$i \neq j$,则$(X_i,Y_i) \neq (X_j,Y_j)$。

输入

输入以以下格式从标准输入给出:

$N$
$X_1$ $Y_1$
$X_2$ $Y_2$
$\dots$
$X_N$ $Y_N$

输出

打印答案为整数。


样例输入 1

4
0 1
1 3
1 1
-1 -1

样例输出 1

3

下图展示了这些点。

有三种方式可以选择形成三角形的点:$\{1,2,3\},\{1,3,4\},\{2,3,4\}$。


样例输入 2

20
224 433
987654321 987654321
2 0
6 4
314159265 358979323
0 0
-123456789 123456789
-1000000000 1000000000
124 233
9 -6
-4 0
9 5
-7 3
333333333 -333333333
-9 -1
7 -10
-1 5
324 633
1000000000 -1000000000
20 0

样例输出 2

1124

加入题单

算法标签: