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




# 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

Your feedback is our precious!

Or call +88 02 9853138 for support