boj2261 가장 가까운 두 점

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

2261번: 가장 가까운 두 점

 

전반적인 개요는 

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

 

 

#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;
 
 
 
}