Dotcpp  >  编程题库  >  蓝桥杯2024年第十五届决赛真题-蚂蚁开会
题目 3290:

蓝桥杯2024年第十五届决赛真题-蚂蚁开会

时间限制: 2s 内存限制: 192MB 提交: 269 解决: 59

题目描述

二维平面上有 n 只蚂蚁,每只蚂蚁有一条线段作为活动范围,第 i 只蚂蚁的活动范围的两个端点为 (uix, uiy),(vix, viy)。现在蚂蚁们考虑在这些线段的交点处设置会议中心。为了尽可能节省经费,它们决定只在所有交点为整点的地方设置会议中心,请问需要设置多少个会议中心?

输入格式

输入共 n + 1 行。第一行为一个正整数 n。后面 n 行,每行 4 个由空格分开的整数表示 uix, uiy, vix, viy。

输出格式

输出共 1 行,一个整数表示答案。

样例输入

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

样例输出

2

提示

【样例说明】

所有线段之间共有 3 个不同的交点:(0, 4),(43,43),(2, 2), 其中整点有 2 个:(0, 4),(2, 2)。

【评测用例规模与约定】

对于 20% 的评测用例,保证 0 ≤ uix, uiy, vix, viy ≤ 100。对于 100% 的评测用例,保证 n ≤ 500,0 ≤ uix, uiy, vix, viy ≤ 10000,保证任意蚂蚁的活动范围不会退化成一个点,不保证任意两条线段之间交点数量有限。

标签