Problem Solving►UVa

UVa 10245 - The Closest Pair Problem

Contents

  1. 1. Problem
  2. 2. Solution
  3. 3. Code

Problem

題目網址
中文網址

找最近點對。

Solution

這裡用兩種方法解，一個是掃描線，另一個就是 DnC 了。
詳細方法可看這裡。

Code

Sweep line

UVa 10245(1)UVa 10245(1) - The Closest Pair Problem
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include<cstdio>
#include<algorithm>
#include<cmath>
struct Point
{
    double x, y;
    double getLen(const Point& a)
    {
        return sqrt((a.x - x)*(a.x - x) + (a.y - y)*(a.y - y));
    }

}point[10000];
int main()
{
    int n, i;
    while (scanf("%d", &n) && n)
    {
        for (i = 0; i < n; i++)
            scanf("%lf%lf", &point[i].x, &point[i].y);

        std::sort(point, point + n, [](const Point& a, const Point& b)->bool{return a.x < b.x; });

        double ans = 10000;
        for (i = 0; i < n; i++)
            for (int j = i + 1; j < n; j++)
            {
            if (point[i].x + ans < point[j].x)//距離大於 此點 + 目前最短距離，兩點距離不可能小於目前最短距離
                break;
            double d = point[i].getLen(point[j]);
            if (d < ans)
                ans = d;
            }

        if (ans == 10000)
            puts("INFINITY");
        else
            printf("%.4lf\n", ans);
    }

    return 0;
}

DnC

UVa 10245(2)UVa 10245(2) - The Closest Pair Problem
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include<cstdio>
#include<algorithm>
#include<cmath>
#define N 10000
#define MAX 10000
using namespace std;

struct Point
{
    double x, y;
    double getLen(const Point& a)
    {
        return sqrt((a.x - x)*(a.x - x) + (a.y - y)*(a.y - y));
    }

}point[N];

double DnC(int L, int R);
int main()
{
    int n, i;
    while (scanf("%d", &n) && n)
    {
        for (i = 0; i < n; i++)
            scanf("%lf%lf", &point[i].x, &point[i].y);

        sort(point, point + n, [](const Point& a, const Point& b)->bool{return a.x < b.x; });

        double ans = DnC(0, n - 1);

        if (ans == 10000)
            puts("INFINITY");
        else
            printf("%.4lf\n", ans);

    }

    return 0;
}
double DnC(int L, int R)
{
    int i, j;
    if (L >= R)//只有一個點
        return MAX;
    else if (R - L < 3)//2 或 3 個點
    {
        double d = MAX;
        for (i = L; i < R; i++)
            for (j = i + 1; j <= R; j++)
                d = min(d, point[i].getLen(point[j]));
        return d;
    }

    int M = (L + R) / 2;

    //左右兩側的最短距離
    double d = min(DnC(L, M), DnC(M + 1, R));
    if (d == 0)
        return 0;

    int n = 0;
    Point strip[N];
    //尋找靠近中線的點，離中線小於目前最短距離 d
    for (i = M; i >= L&&point[M].x - point[i].x < d; i--)
        strip[n++] = point[i];
    for (i = M + 1; i <= R&&point[i].x - point[M].x < d; i++)
        strip[n++] = point[i];

    //依 y 軸排序
    sort(strip, strip + n, [](const Point& a, const Point& b)->bool{return a.y < b.y; });

    //找出橫跨兩側的最短距離
    for (i = 0; i < n; i++)
        for (j = 1; j <= 3 && i + j < n; j++)
            d = min(d, strip[i].getLen(strip[i + j]));

    return d;
}