ACM14KP1 - Editorial

editorial
, , , ,
1

PROBLEM LINK:

Practice
Contest

Author: Jingbo Shang
Tester: Anudeep Nekkanti
Editorialist: Jingbo Shang

DIFFICULTY:

Easy-Medium

PREREQUISITES:

Sort, Divide and Conquer

PROBLEM:

Given N points in a plane, find out three points A, B and C such that |AB| + |BC| + |CA is smallest.

EXPLANATION:

Classical 2 points (Closest Points)

This is a classical problem that finding out the closest 2 points. We can deal with that using divide and conquer.

Initially, we sort all the points P[1…N] by their X values, from small to large.

Now, suppose we are handling the answer in points between indices l and r, i.e. the closest points in P[l…r].. First of all, we divide them into 2 parts and recursively calculate the closest points problem. That is, find out the answer in P[l…m] and P[m+1…r]. Assume the minimum answer is A. Then, we try to update the answer using the points from different parts, i.e. |P[i] – P[j]|, where l <= i <= m < j <= r. Instead of bruteforce enumeration, we can use the current answer A to prune. It is easy to prove that there are only a small constant of points within the square [P[i].x, P[i].x + A] X [P[i].y, P[i].y + A] (Otherwise, the current minimum should be less than A). Therefore, we can further sort the points in P[l…r] in the order of Y coordinate, scan them one by one, and use the bruteforce enumeration inside the small square to update the answer.

If we use quick sort every time, the time complexity should be O(Nlog^2N). However, we can apply merge sort for the sorting of Y values, and thus the time complexity could be reduced to O(NlogN).

Original Question

Similar ideas could be applied to 3 points. The only difference is that the constant bound of the points in that small square may be different.

It is an accident that both setter and tester did not realize there existed a same problem in Google Codejam 2009 Finals. You can also check their editorials for more information.

AUTHOR’S AND TESTER’S SOLUTIONS:

Solutions will be available soon.

Author’s solution can be found here.
Tester’s solution can be found here.

1 Like
2

please correct me…
what I did was for the problem was that I compute a side and then i keep track of the minimum three sides thus obtained, i am getting a wrong answer for the problem.

thanx in advance :slight_smile:

3

This is my solution in C++.

Reference - Closest Pair of Points using Divide and Conquer algorithm - GeeksforGeeks

#include <bits/stdc++.h>
using namespace std;

#define d double
#define M 100010

class Point
{
public:
    d x,y;
};

Point pt[M];
Point strip[M];

bool cmpx(Point &a, Point &b){
    return a.x < b.x;
}

bool cmpy(Point &a, Point &b){
    return a.y < b.y;
}

d dist(Point &a, Point &b){
    d x1,x2,y1,y2;
    x1 = a.x; x2 = b.x;
    y1 = a.y; y2 = b.y;
    return sqrt((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1));
}

d perimeter(Point &a, Point &b, Point &c){
    return dist(a,b)+dist(b,c)+dist(a,c);
}

d ClosestPair(int s, int e){
    if(s == e)
        return 1e9;
    if(s+1 == e)
        return 1e9;
    if(s+2 == e)
        return perimeter(pt[s],pt[s+1],pt[s+2]);

    int mid = s + (e-s)/2;
    d d1 = ClosestPair(s,mid);
    d d2 = ClosestPair(mid+1,e);
    d d_min = min(d1,d2);
    Point m = pt[mid];
    int idx=0;
    for(int i=s; i<=e; i++)
    {
        if( abs(pt[i].x - m.x) < d_min)
            strip[idx++] = pt[i];
    }

    sort(strip, strip+idx, cmpy);

    for(int i = 0; i < idx ; i++)
    {
        for(int j = i+1; j < idx && (strip[j].y - strip[i].y)<d_min; j++)
        {
            for(int k = j+1; k < idx && (strip[k].y - strip[j].y)<d_min; k++)
            {
                d_min = min(d_min, perimeter(strip[i],strip[j],strip[k]));
            }
        }
    }
    return d_min;
}

int main(){
    int  t;
    cin >> t;
    for(int i =1; i<=t; i++)
    {
        int n;
        cin >> n;
        for(int i = 0; i<n; i++)
            cin >> pt[i].x >> pt[i].y;
        sort(pt, pt+n, cmpx);
        cout<<fixed<<setprecision(10)<<"Case "<<i<<": "<<ClosestPair(0,n-1)<<endl;
    }
	return 0;
}
1 Like