#P18822. [Croatian CPC2017] Asfalt
[Croatian CPC2017] Asfalt
[Croatian CPC2017] Asfalt
题目描述
某座城市建在一个三角形网格上。坐标系的 轴与 轴夹角为 ,两个坐标轴的单位长度相同,如图所示。坐标均为整数的两个点,如果欧几里得距离为 ,就称为相邻点。每个点恰好有六个相邻点。
城市中有 条小路,每条小路连接一对相邻点。现在希望把尽可能多的小路铺成柏油路,但不能出现急转弯:任意两条铺好的路如果在一个端点相接,它们在该点形成的夹角都不能是锐角。
求最多可以铺多少条路。
输入格式
第一行包含一个整数 (),表示小路数量。
接下来 行,每行包含四个整数 (均在 内),表示一条连接点 与 的小路。
保证每条小路连接两个相邻点,且没有重复的小路。
输出格式
输出一个整数,表示最多可以铺成柏油路的小路数量。
样例 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
样例说明
下图展示了三角形网格、坐标轴及样例中的道路。
