二维平面上有 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,保证任意蚂蚁的活动范围不会退化成一个点,不保证任意两条线段之间交点数量有限。