[UVA] 10245 - The Closest Pair Problem

題目連結

須注意的是距離 = 0 時直接return

*********************************************
程式碼:

/* 題目: UVa 10245 - The Closest Pair Problem
 * Language: C++
 * Created on: 2016年10月07日
 *   Author: hanting
 */
#include <iostream>
#include <vector>
#include <algorithm> //sort, lower_bound
#include <cmath> // sqrt
#include <iomanip> // setprecision
using namespace std;
struct Point
{
    double x, y;
    Point(double _x = 0, double _y = 0)
    {
        x = _x;
        y = _y;
    }
    bool operator < (const Point &p)const
    {
        return x < p.x || (x == p.x && y < p.y);
    }
    friend istream& operator >> (istream& in, Point &p)
    {
        in >> p.x >> p.y;
        return in;
    }
};
bool checkInRange(Point &a, Point &b, double &d) // 判斷是否在需要判斷範圍
{
    return a.y + d >= b.y && a.y - d <= b.y;
}
double dis(Point &a, Point &b)
{
    double x, y;
    x = a.x - b.x;
    y = a.y - b.y;
    return sqrt(x*x + y*y);
}
double ClosestPair(vector<Point>::iterator Begin, vector<Point>::iterator End)
{

    double closest = 0x3fffffff;
    if(Begin+1 == End)
    {
        return closest;
    }
    else if(Begin + 2 == End)
    {
        return dis(*Begin, *(Begin+1));
    }
    double SL, SR;
    SL = ClosestPair(Begin, Begin+(End-Begin)/2);
    SR = ClosestPair(Begin+(End-Begin)/2, End);

    double d, L;
    d = min(SL, SR);
    if(!d) return 0;
    L = (Begin+(End-Begin)/2)->x;
    closest = d;
    for(vector<Point>::iterator it = lower_bound(Begin, End, L-d);
    it != (Begin+(End-Begin)/2); ++it)
    {
        for(vector<Point>::iterator j = (Begin+(End-Begin)/2), jEnd = lower_bound(Begin, End, L+d);
        j != jEnd; j++)
        {
            if(checkInRange(*it, *j, d))
            {
                closest = min(closest, dis(*it, *j));
            }
        }
    }
    return closest;
}
int main()
{
    int pointN;
    while(cin >> pointN && pointN)
    {
        vector<Point> vec;
        for(int i = 0; i < pointN; i++)
        {
            Point tmp;
            cin >> tmp;
            vec.push_back(tmp);
        }
        sort(vec.begin(), vec.end());
        double ans = ClosestPair(vec.begin(), vec.end());
        if(ans < 10000.0)
            cout << fixed << setprecision(4) << ans << endl;
        else
            cout << "INFINITY" << endl;
    }
    return 0;
}

**************************************************
不用Vector且以scanf, printf輸入輸出，時間較快
/* 題目: UVa 10245 - The Closest Pair Problem
 * Language: C++
 * Created on: 2016年10月07日
 *   Author: hanting
 */
#include <iostream>
#include <cstdio>
#include <algorithm> //sort, lower_bound
#include <cmath> // sqrt
#include <iomanip> // setprecision
using namespace std;
struct Point
{
    double x, y;
    Point(double _x = 0, double _y = 0)
    {
        x = _x;
        y = _y;
    }
    bool operator < (const Point &p)const
    {
        return x < p.x || (x == p.x && y < p.y);
    }
};
bool checkInRange(Point &a, Point &b, double &d) // 判斷是否在需要判斷範圍
{
    return a.y + d >= b.y && a.y - d <= b.y;
}
double dis(Point &a, Point &b)
{
    double x, y;
    x = a.x - b.x;
    y = a.y - b.y;
    return sqrt(x*x + y*y);
}
double ClosestPair(Point *Begin, Point *End)
{
    double closest = 0x3fffffff;
    if(Begin+1 == End)
    {
        return closest;
    }
    else if(Begin + 2 == End)
    {
        return dis(*Begin, *(Begin+1));
    }
    double SL, SR;
    SL = ClosestPair(Begin, Begin+(End-Begin)/2);
    SR = ClosestPair(Begin+(End-Begin)/2, End);

    double d, L;
    d = min(SL, SR);
    if(!d) return 0;
    L = (Begin+(End-Begin)/2)->x;
    closest = d;
    for(Point *it = lower_bound(Begin, End, L-d);
    it != (Begin+(End-Begin)/2); ++it)
    {
        for(Point *j = (Begin+(End-Begin)/2), *jEnd = lower_bound(Begin, End, L+d);
        j != jEnd; j++)
        {
            if(checkInRange(*it, *j, d))
            {
                closest = min(closest, dis(*it, *j));
            }
        }
    }
    return closest;
}
int main()
{
    int pointN;
    Point arr[10005];
    while(cin >> pointN && pointN)
    {
        int arri = 0;
        for(int i = 0; i < pointN; i++)
        {
            double a, b;
            scanf("%lf%lf", &a, &b);
            arr[arri++] = Point(a, b);
        }
        sort(arr, arr+arri);
        double ans = ClosestPair(arr, arr+arri);
        if(ans < 10000.0)
            printf("%.4lf\n",ans);
        else
            puts("INFINITY");
    }
    return 0;
}