레이팅 미적용In the town of Nattanham, all roads run either north to south, or east to west, and span the entire town. Furthermore, all roads are an equal distance apart. This makes navigating the town extremely easy.
Unfortunately, the roads are quite poor and could do with a fresh layer of asphalt. However, there is not enough money to fix all the roads, so some sections of road need to be given priority.
The mayor has selected five locations in town that he considers to be of great importance: the city hall, the police station, the hospital, the fire department, and of course the mayor's house. Each of these locations is at an intersection.
The mayor wishes that, for each pair of these important locations, it becomes possible to get from one to the other along a shortest path that consists entirely of refurbished road. Within this restriction, the mayor would like to refurbish the smallest amount of road. The intersections do not count toward this amount. Figure depicts an optimal configuration of refurbished roads.
Input The input consists of:
- Five lines, each with two integers \(x\) and \(y\) (\(0 \le x, y \le 1000\)), the grid coordinates of each of the five important locations.
It is guaranteed that the locations are distinct. Input
Output
Output the minimum number of road segments that need to be refurbished.
8 1
3 4
6 7
10 4
1 2
22
0 0
0 10
20 0
20 10
3 3
70