1423 . 直線線段相交問題 (Intersection)
TopCoder
Tags
Description
原題目敘述
在直角坐標平面上有 $N$ 個相異格子點 $A_1 = (x_1, y_1), A_2 = (x_2, y_2), \cdots, A_n = (x_n, y_n)$。
請你寫一個程式，計算有多少組正整數四元組 $a, b, c, d$ 滿足 $a, b, c, d, \leq N; a < b; c < d$ ，
且直線線段對 $(\overleftrightarrow{A_a A_b}, \overline{A_c A_d})$ 恰交於一個 $\overline{A_c A_d}$ 的內點。
（一個線段的內點即是在線段內但不是端點的點。）
Input Format
第一行有一個正整數 $N$，代表點數。接下來 $N$ 行中，每一行都有兩個整數 $x_i, y_i$，代表 $A_i = (x_i, y_i)$。
保證對於所有測資，$|x_i|, |y_i| \leq 10000$。
Output Format
請輸出一行包含一個整數，代表滿足題意的正整數四元組個數。
Sample Input 1
5
0 0
1 1
-1 -1
-1 2
2 1
0 0
1 1
-1 -1
-1 2
2 1
Sample Output 1
11
Sample Input 2
6
0 0
0 1
1 0
1 1
2 2
-2 2
0 0
0 1
1 0
1 1
2 2
-2 2
Sample Output 2
33
Hints
Problem Source
Problem Set / Description by Paupière
建國中學105學年度北市賽模擬賽pB
2021.02.17 Update: Added 題目敘述 by FHVirus
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~4 | $N \leq 10$ | 10 |
| 2 | 0~9 | $N \leq 100$ | 30 |
| 3 | 0~14 | $N \leq 350$ | 60 |