report VI VI EN
Register | Login
  • HOME
  • PROBLEMSET
  • ROADMAP
  • COMPETITION
  • TOPIC
  • RANKING
  • GUIDE
  • MASHUP
  • ABOUT
  • CONTACT
  • Problem
  • Submit
  • Results
Closest pair - MarisaOJ: Marisa Online Judge

Closest pair

Time limit: 1000 ms
Memory limit: 256 MB
Given $n$ points on a two-dimensional coordinate grid. Calculate the square of the distance between the two closest points. ### Input - The first line contains an integer $n$. - The next $n$ lines each contain two integers $(x, y)$, representing a point at coordinates $(x, y)$. Ensure that no two points have the same position. ### Output - Print an integer representing the square of the distance between the two closest points. ### Constraints - $1 \leq n \leq 3 \times 10^5$. - $1 \leq x, y \leq 10^9$. ### Example Input: ``` 4 1 1 1 4 3 2 4 3 ``` Output: ``` 2 ```
Sweep Line
Intersections
Radio
Area
Square
Closest pair
Triangle
Paper cutting
Topic
Data structure
Rating 2100
Solution (0) Solution