뚝배기 터진 문제_boj

boj2261 가장 가까운 두 점

헐랭미 2020. 6. 12. 16:40

https://www.acmicpc.net/problem/2261

 

2261번: 가장 가까운 두 점

첫째 줄에 자연수 n(2 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 줄에는 차례로 각 점의 x, y좌표가 주어진다. 각각의 좌표는 절댓값이 10,000을 넘지 않는 정수이다. 같은 점이 여러 번 주어질 수도 있��

www.acmicpc.net

 

전반적인 개요는 

set<pii, comp> s = { p[0], p[1] };  -> 초기 저장 
int ans = dist(p[0], p[1]);     -> 초기 두 점의 거리 최솟값
int start = 0;         -> 기준점

 

 

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
79
80
81
82
83
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <cmath>
#define pii pair<int, int>
 
using namespace std;
 
pii p[100000];
 
class comp
{
public :
    bool operator() (const pii& p1, const pii& p2) const
    {
        if (p1.second == p2.second)
            return p1.first < p2.first;
        else
            return p1.second < p2.second;
    }
};
 
int dist(pii a, pii b)
{
    return (b.first - a.first) * (b.first - a.first) + (b.second - a.second) * (b.second - a.second);
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
 
 
    int n;
    cin >> n;
 
    for (int i = 0; i < n; i++)
        cin >> p[i].first >> p[i].second;
    
    sort(p, p + n);
 
    set<pii, comp> s;
    s.insert(p[0]);
    s.insert(p[1]);
    int ans = dist(p[1], p[0]);  //초기값
    int start = 0;                 // base
    for (int i = 2; i < n; i++)
    {
        pii cur = p[i];     
        while (start < i)
        {
            int t_x = p[i].first - p[start].first;
            if (t_x * t_x > ans) // (p[i].x - p[start].x)^2 이 ans보다 크면 정답과 벗어나니 빼준다.
            {
                s.erase(p[start]);
                start++;
            }
            else
                break;
        }
        int tmp = sqrt(ans) + 1;
        pii lower = {-100000, cur.second-tmp }; //p[i].y-sqrt(ans) ~ p[i].y+sqrt(ans)의 y값을 범위로
        pii upper = {100000 , cur.second+tmp };
 
        set<pii>::iterator itrlower = s.lower_bound(lower);
        set<pii>::iterator itrupper = s.upper_bound(upper);
 
        for (itrlower; itrlower != itrupper; itrlower++)
        {
            int d = dist(*itrlower, cur);    //dist를 탐색한다.
            if (ans > d)
                ans = d;
                
        }
        s.insert(cur);
 
    }
    cout << ans;
 
 
 
}
cs