[ boj : 14746 ] Closet Pair

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

14746번: Closest Pair

문제 해석 : n과 m 이 주어집니다. n개의 점들은 P 의 집합에 속하게 되고, m개의 점들은 Q의 집합에 속하게 됩니다. 이때 y축과 평행한 C1과 C2 두개의 선이 주어집니다.

 

이럴때 P 의 집합에 속한 좌표와 Q의 집합에 속한 좌표의 거리의 차이값 중 최소값을 찾고 그런점들의 개수를 구하면 됩니다.

 

(p1,C1),(p2,C1) ,,,,,

(q1,C2),(q2,C2) ,,,,,

 

해설 : 어차피 두 좌표를 선택하면 y축의 거리는 고정되어 있는 거리입니다. 그러면 그냥 C1과 C2의 거리의 차이로 구할 수 있습니다.

 

그럼 x 좌표들끼리의 차이만 구하면 됩니다. 이는 그냥 수평선 하나를 긋고 거기에 점들을 찍어서 서로 다른 집합에 속한 점들이면 거리를 갱신하는 방법으로 충분히 구할 수 있습니다.

 

#include<bits/stdc++.h>

using namespace std;

int main()
{
    int n, m;
    int c1, c2;
    vector<pair<int, int>> v;
    map<int, int> mp;

    cin >> n >> m >> c1 >> c2;
    int input;
    for (int i = 0; i < n; i++) {
        cin >> input;
        v.push_back({ input,0 });
    }
    for (int i = 0; i < m; i++) {
        cin >> input;
        v.push_back({ input,1 });
    }
    sort(v.begin(), v.end());

    int x = abs(c1 - c2);
    int Max, dis, flag;

    Max = v[0].first;
    dis = 0;
    flag = v[0].second;
    for (int i = 1; i < v.size(); i++) {
        if (flag != v[i].second) {
            dis = abs(Max - v[i].first);
            mp[dis] += 1;
            flag = v[i].second;
            Max = v[i].first;
        }
        else {
            Max = v[i].first;
        }
    }
    /*for (auto u : mp)
        cout << u.first << " " << u.second << "\n";*/
    auto u = mp.begin();
    cout << u->first + x<<" "<<u->second;
    return 0;
}