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 ≤ 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≤12000, 2 ≤ n ≤ 10<sup>5</sup> Sum of n over all test case is less than or equal 10<sup>6</sup> -10<sup>9</sup> ≤ xi , yi ≤ 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 ≤ x2. if x1==x2, then y1≤ 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

Md. Tariqul Islam