백준16885 벡터의 합

작성일 | In

문제 링크

  • http://icpc.me/16885

시간복잡도

  • $O(N \log N)$

풀이

두 벡터가 서로 반대 방향 사분면에 위치하는 경우가 최적이라는 것은 쉽게 알 수 있습니다.

사분면을 마음대로 결정할 수 있으므로 모든 벡터를 1사분면으로 옮기면, 1사분면 상의 벡터 $(x_1, y_1)$과 3사분면으로 이동시킨 벡터 $(-x_2, -y_2)$를 더한 결과 $(x_1-x_2, y_1-y_2)$의 길이는 $\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}$입니다. 결국 모든 점을 1사분면으로 옮긴 다음 가장 가까운 두 점을 구하면 문제를 해결할 수 있습니다.

전체 코드

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
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct Point{
    ll x, y, i, op;
    bool operator < (const Point &p) const { return tie(x,y) < tie(p.x,p.y); }
};

int N;
Point A[101010];

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N;
    for(int i=1; i<=N; i++){
        int x, y, d = 1; cin >> x >> y;
        if(x < 0 && y < 0) d = 4, x = -x, y = -y;
        else if(x < 0) d = 2, x = -x;
        else if(y < 0) d = 3, y = -y;
        assert(x >= 0 && y >= 0);
        A[i] = {x+y, x-y, i, d};
    }
    sort(A+1, A+N+1);
    ll res = 0x3f3f3f3f3f3f3f3f, a = -1, b = -1;
    for(int i=1; i<=N; i++){
        for(int j=i-1; j>=1; j--){
            ll dx = A[i].x - A[j].x, dy = A[i].y - A[j].y;
            if(dx*dx >= res) break;
            ll now = dx*dx + dy*dy;
            if(now < res) res = now, a = i, b = j;
        }
    }
    cout << A[a].i << " " << 5 - A[a].op << " " << A[b].i << " " << A[b].op;
}