Problem Solving►UVa

UVa 11378 - Bey Battle

Contents

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

Problem

題目網址

給你點的位置，求出以各個點為中心的正方形，邊長最多可達多少?每個正方形邊長須一樣，可剛好接觸到。

Solution

只要求出最近兩點之間的距離即為邊長(除以2又乘以2)。

一開始用掃描線的做法就 AC 了，不過後來得知可能在某些測資會超時。就補做了 D&C。這裡一併附上。

Code

掃描線

UVa 11378UVa 11378 - Bey Battle
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
#include<cstdio>
#include<algorithm>
#include<cmath>
#define N 100000
using namespace std;
struct Point
{
    int x, y;
    int getSide(const Point& a){ return max(abs(x - a.x), abs(y - a.y)); }

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

        sort(point, point + n, [](const Point& a, const Point& b)->bool{return a.x < b.x; });
        int min = 1e9;
        for (i = 0; i < n; i++)
        {
            for (j = i + 1; j < n; j++)
            {
                if (point[i].x + min < point[j].x)
                    break;

                int temp = point[i].getSide(point[j]);
                if (temp < min)
                    min = temp;
            }
        }

        printf("%d\n", min);
    }

    return 0;
}

D&C

UVa 11378UVa 11378 - Bey Battle
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
#include<cstdio>
#include<algorithm>
#include<cmath>
#define N 100000
#define MAX 1e9
using namespace std;
struct Point
{
    int x, y;
    int getSide(const Point& a){ return max(abs(x - a.x), abs(y - a.y)); }

}point[N];

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

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

        printf("%d\n", DnC(0, n - 1));
    }

    return 0;
}
int DnC(int L, int R)
{
    if (L >= R)
        return MAX;
    else if (R - L < 3)
    {
        int d = MAX;
        for (int i = L; i < R; i++)
            for (int j = i + 1; j <= R; j++)
                d = min(d, point[i].getSide(point[j]));
        return d;
    }

    int M = (L + R) >> 1, i, j;

    int d = min(DnC(L, M), DnC(M + 1, R));
    //每個左側的點，到右側的點
    for (i = M; i >= L; i--)
    {
        if (point[M].x - point[i].x >= d)
            break;
        for (j = M + 1; j <= R; j++)
        {
            if (point[j].x - point[M].x >= d)
                break;
            int temp = point[i].getSide(point[j]);
            if (temp < d)
                d = temp;
        }
    }

    return d;
}