推荐题目：洛谷 P10907 [蓝桥杯 2024 国 B] 蚂蚁开会

P10907 [蓝桥杯 2024 国 B] 蚂蚁开会

在洛谷，可提交！

题目描述

二维平面上有

n

n

n 只蚂蚁，每只蚂蚁有一条线段作为活动范围，第

i

i

i 只蚂蚁的活动范围的两个端点为

(

u

i

x

,

u

i

y

)

,

(

v

i

x

,

v

i

y

)

(u_i^ x,u_i^y), (v_i^x,v_i^y)

(uix​,uiy​),(vix​,viy​)。现在蚂蚁们考虑在这些线段的交点处设置会议中心。为了尽可能节省经费，它们决定只在所有交点为整点的地方设置会议中心，请问需要设置多少个会议中心？

输入格式

输入共

n

+

1

n + 1

n+1 行。

第一行为一个正整数

n

n

n。

后面

n

n

n 行，每行

4

4

4 个由空格分开的整数表示

u

i

x

,

u

i

y

,

v

i

x

,

v

i

y

u_i^x, u_i^y,v_i^x,v_i^y

uix​,uiy​,vix​,viy​。

输出格式

输出共

1

1

1 行，一个整数表示答案。

输入输出样例 #1

输入 #1

4
0 0 4 4
0 4 4 0
2 0 0 4
2 1 2 3

输出 #1

2

说明/提示

【样例说明】

所有线段之间共有

3

3

3 个不同的交点：

(

0

,

4

)

,

(

4

3

,

4

3

)

,

(

2

,

2

)

(0, 4), (\\frac{4}{3}, \\frac{4}{3}), (2, 2)

(0,4),(34​,34​),(2,2), 其中整点有

2

2

2 个：

(

0

,

4

)

,

(

2

,

2

)

(0, 4), (2, 2)

(0,4),(2,2)。

【评测用例规模与约定】

对于

20

%

20\\%

20% 的评测用例，保证

0

≤

u

i

x

,

u

i

y

,

v

i

x

,

v

i

y

≤

100

0 \\le u_i^x, u_i^y, v_i^x, v_i^y\\le 100

0≤uix​,uiy​,vix​,viy​≤100。 对于

100

%

100\\%

100% 的评测用例，保证

n

≤

500

n \\le 500

n≤500，

0

≤

u

i

x

,

u

i

y

,

v

i

x

,

v

i

y

≤

10000

0 \\le u_i^x, u_i^y, v_i^x, v_i^y \\le 10000

0≤uix​,uiy​,vix​,viy​≤10000，保证任意蚂蚁的活动范围不会退化成一个点，不保证任意两条线段之间交点数量有限。