Graph on a Plane
Limits: 4 sec., 512 MiB
You are given \(n\) unique points \((x_i, y_i)\) 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 \((x_i, y_i)\) and \((x_j, y_j)\).
Find the minimum number of edges in a good graph.
Input
The first line contains an integer \(n\) – the number of points.
The following \(n\) lines contain two integers \(x_i\) and \(y_i\) – coordinates of the points.
Output
In a single line, print an integer – the minimum number of edges in a good graph.
Constraints
\(1 \le n \le 2000\),
\(|x_i|, |y_i| \le 10^9\).
All points are distinct.
Samples
| Input (stdin) | Output (stdout) |
|---|---|
| 4 0 0 4 3 4 2 0 4 | 6 |
| Input (stdin) | Output (stdout) |
|---|---|
| 5 0 0 1 0 0 2 -3 0 0 -4 | 8 |
Notes
Submit a solution
| Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
|---|
| Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
|---|