#P18822. [Croatian CPC2017] Asfalt

[Croatian CPC2017] Asfalt

[Croatian CPC2017] Asfalt

题目描述

某座城市建在一个三角形网格上。坐标系的 xx 轴与 yy 轴夹角为 60∘60^\circ,两个坐标轴的单位长度相同,如图所示。坐标均为整数的两个点,如果欧几里得距离为 11,就称为相邻点。每个点恰好有六个相邻点。

城市中有 nn 条小路,每条小路连接一对相邻点。现在希望把尽可能多的小路铺成柏油路,但不能出现急转弯:任意两条铺好的路如果在一个端点相接,它们在该点形成的夹角都不能是锐角。

求最多可以铺多少条路。

输入格式

第一行包含一个整数 nn(1≤n≤10001\le n\le1000),表示小路数量。

接下来 nn 行,每行包含四个整数 xA,yA,xB,yBx_A,y_A,x_B,y_B(均在 [1,100][1,100] 内),表示一条连接点 A=(xA,yA)A=(x_A,y_A) 与 B=(xB,yB)B=(x_B,y_B) 的小路。

保证每条小路连接两个相邻点,且没有重复的小路。

输出格式

输出一个整数,表示最多可以铺成柏油路的小路数量。

样例 1

输入

17
1 1 2 1
1 1 1 2
3 2 4 2
3 2 2 2
3 2 3 3
3 2 3 1
3 2 4 1
3 2 2 3
4 1 3 1
3 1 2 1
1 2 1 3
1 3 2 3
3 3 4 2
4 2 4 1
1 2 2 2
4 2 5 2
2 4 3 4

输出

10

样例说明

下图展示了三角形网格、坐标轴及样例中的道路。

三角形网格示意图