DCP-499: Closest Pair Point Back to All Problems

Hard Data Structures > Orthogonal Range Search


You are given n points in a 2D plane. Find the closest pair of point p1(x1,y1) , p2(x2,y2) where x1 &le; x2 such that there is no such point p3(x3,y3) where x1 < x3 < x2 . In other word, if you draw two vertical line (parallel to y axis) x=x1 and x=x2 , then there should not be any point between them. Input: ------ First line of input file will contain a integer number of test cases T, Each test case will start with a number n , the total number of point. Next n line will contain 2 integer each (xi , yi ) to denote the i’th point. T&le;12000, 2 &le; n &le; 10<sup>5</sup> Sum of n over all test case is less than or equal 10<sup>6</sup> -10<sup>9</sup> &le; xi , yi &le; 10<sup>9</sup> All point in a test case will be distinct Output: ------- For each test case you have to print 5 space separated integer . d x1 y1 x2 y2 Where d is the squared distance between p1 and p2, (x1,y1) is the coordinate of p1 and (x2,y2) is the coordinate of p1. Note that x1 &le; x2. if x1==x2, then y1&le; y2 If there is multiple such pair of point then choose lexicographically smallest one. ( d x1 y1 x2 y2 should be lexicographically smallest over all answer ) Sample Input ------------ 2 3 1 100 2 50 100 100 4 1 150 1 100 50 100 50 150 Sample Output ------------- 2501 1 100 2 50 2401 1 100 50 100


Problem Setter:

Md. Tariqul Islam

Please login to submit solution to this problem.

Problem Limits

Language Time Limit (seconds)
C 2.00
C++ 2.00
C++14 2.00
C# 3.00
Go 3.00
Java 3.00
JavaScript 3.00
Objective-C 3.00
Perl 3.00
PHP 3.00
Python 3.00
Python3 3.00
Ruby 3.00
VB.Net 3.00

Problem Stats

8/68

Solve/Submission

Ranking

# User Language Timing
01 tariqiitju Cpp 0.57s
02 mahbubcseju Cpp 0.93s
03 Robbinb1993 Cpp14 1.31s
04 Morass Cpp14 1.58s
05 Tahmid Cpp14 1.68s
Feedback

Your feedback is our precious!



Or call +88 02 9853138 for support