Graph on a Plane
Обмеження: 4 сек., 512 МіБ
You are given n unique points (xi,yi) on a two-dimensional plane.
A weighted undirected graph G with real-valued weights is good if it satisfies the following conditions.
G contains n vertices numbered 1 through n.
For each pair of vertices (i,j), the shortest-path weight between vertices i and j in G equals the Euclidean distance between points (xi,yi) and (xj,yj).
Find the minimum number of edges in a good graph.
Вхідні дані
The first line contains an integer n – the number of points.
The following n lines contain two integers xi and yi – coordinates of the points.
Вихідні дані
In a single line, print an integer – the minimum number of edges in a good graph.
Обмеження
1≤n≤2000,
|xi|,|yi|≤109.
All points are distinct.
Приклади
Вхідні дані (stdin) | Вихідні дані (stdout) |
---|---|
4 0 0 4 3 4 2 0 4 | 6 |
Вхідні дані (stdin) | Вихідні дані (stdout) |
---|---|
5 0 0 1 0 0 2 -3 0 0 -4 | 8 |
Примітки
Джерело: Ukrainian National Programming Contest 2024 - Stage 2