184 . 線段與直線

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

wiwiho

User's AC Ratio

100.0% (4/4)

Submission's AC Ratio

17.1% (6/35)

Tags

ioicamp ioicamp-2022

Description

給定 $N$ 個二維平面上線段（有可能退化成點），請你找出一條直線，使得這條直線跟最多的線段相交於至少一個點。

為了方便，你只要輸出數量（那條直線跟多少個線段相交於一個點）就可以了。

Input Format

輸入的第一行包含一個正整數 $N$，代表線段的個數。

接下來的 $N$ 行，每行包含四個整數 $x_1, y_1, x_2, y_2$，代表有一個線段是從 $(x_1, y_1)$ 到 $(x_2, y_2)$。

  • $1 \leq N \leq 1500$
  • $0 \leq x_1, y_1, x_2, y_2 \leq 10^ 9$

Output Format

輸出一個整數於一行，代表跟題目敘述要求的那個數字。

Sample Input 1

4
1 1 3 4
7 5 7 1
3 6 9 8
2 3 2 4

Sample Output 1

3

Sample Input 2

5
1 1 1 1
1 1 1 1
1 2 1 2
2 1 2 1
2 1 2 1

Sample Output 2

4

Sample Input 3

1
1 2 3 4

Sample Output 3

1

Hints

Problem Source

IOICamp 2022 Day4 pG

Subtasks

No. Testdata Range Constraints Score
1 0~2 範例測資 0
2 0~27 $N \leq 200$ 40
3 0~42 無額外限制 60

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 4000 524288 65536 1 2 3
1 4000 524288 65536 1 2 3
2 4000 524288 65536 1 2 3
3 4000 524288 65536 2 3
4 4000 524288 65536 2 3
5 4000 524288 65536 2 3
6 4000 524288 65536 2 3
7 4000 524288 65536 2 3
8 4000 524288 65536 2 3
9 4000 524288 65536 2 3
10 4000 524288 65536 2 3
11 4000 524288 65536 2 3
12 4000 524288 65536 2 3
13 4000 524288 65536 2 3
14 4000 524288 65536 2 3
15 4000 524288 65536 2 3
16 4000 524288 65536 2 3
17 4000 524288 65536 2 3
18 4000 524288 65536 2 3
19 4000 524288 65536 2 3
20 4000 524288 65536 2 3
21 4000 524288 65536 2 3
22 4000 524288 65536 2 3
23 4000 524288 65536 2 3
24 4000 524288 65536 2 3
25 4000 524288 65536 2 3
26 4000 524288 65536 2 3
27 4000 524288 65536 2 3
28 4000 524288 65536 3
29 4000 524288 65536 3
30 4000 524288 65536 3
31 4000 524288 65536 3
32 4000 524288 65536 3
33 4000 524288 65536 3
34 4000 524288 65536 3
35 4000 524288 65536 3
36 4000 524288 65536 3
37 4000 524288 65536 3
38 4000 524288 65536 3
39 4000 524288 65536 3
40 4000 524288 65536 3
41 4000 524288 65536 3
42 4000 524288 65536 3
Submit
Back to Top