1423 . 直線線段相交問題 (Intersection)

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

Caido
$\mathbb{W}\mathcal{aimai}\sim$

User's AC Ratio

100.0% (45/45)

Submission's AC Ratio

83.3% (80/96)

Tags

CKsim 2016-CKsim-北市模擬 geometry

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

Sample Output 1

11

Sample Input 2

6
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

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 3000 524288 262144 1 2 3
1 3000 524288 262144 1 2 3
2 3000 524288 262144 1 2 3
3 3000 524288 262144 1 2 3
4 3000 524288 262144 1 2 3
5 3000 524288 262144 2 3
6 3000 524288 262144 2 3
7 3000 524288 262144 2 3
8 3000 524288 262144 2 3
9 3000 524288 262144 2 3
10 3000 524288 262144 3
11 3000 524288 262144 3
12 3000 524288 262144 3
13 3000 524288 262144 3
14 3000 524288 262144 3
Submit
Back to Top