report VI VI EN
Register | Login
  • HOME
  • PROBLEMSET
  • ROADMAP
  • COMPETITION
  • TOPIC
  • RANKING
  • GUIDE
  • MASHUP
  • ABOUT
  • CONTACT
  • Problem
  • Submit
  • Results
Orthogonal pairs - FlandreOJ: Flandre Online Judge

Orthogonal pairs

Time limit: 2000 ms
Memory limit: 256 MB
Given $2n+1$ distinct points $(x_i, y_i)$ on a 2D plane. **Task**: Count the number of points such that if we remove that point, the remaining $2n$ points can be partitioned into $n$ pairs, where each pair shares either the same x-coordinate or the same y-coordinate. #### Input - First line contains integer $n$ ($1 \le n \le 10^5$). - The next $2n+1$ lines each contain two integers $x_i, y_i$ ($0 \le x_i, y_i \le 10^9$). #### Output - Print the number of such points. #### Example Input: ``` 3 0 0 0 1 1 0 1 1 2 2 2 3 3 2 ``` Output: ``` 2 ``` #### Subtasks - **Subtask 1 (17 points)**: $n \le 8$. - **Subtask 2 (18 points)**: $n \le 50$. - **Subtask 3 (25 points)**: $n \le 1000$ and there are at most 2 distinct x-coordinates. - **Subtask 4 (20 points)**: $n \le 1000$. - **Subtask 5 (20 points)**: No additional constraints.
PTNK Team Selection Test [2025 - 2026]
Balanced subarray
Construct number
Orthogonal pairs
Bubble sort
Optimal subset
Water troughs
Topic
2026
Rating 800
Solution (0) Solution