2015年2月15日 星期日

2015/02/15 vijos P1012 清帝之惑之雍正

/*
    平面座標上
    求最近點對

    

    D&C
    因為鴿籠原理
    所以 複雜度是 nlgn
    實在是精妙啊 想不出來=口="


    詳細做法
    按X排序 接著把區間分成兩半
    兩邊的答案 取最小值
    先得到一個 ans



    接著要考慮 最近點對
    在兩區間 各一的情況...

    對於 可能為最小點對的 (p, q)
    其x座標必定分別在 
    [mid-ans, mid] 和 [mid, mid+ans] 之間

    
    把滿足這些條件的點
    存起來 按y值排序
    枚舉 p,q 若y值差
    超過 ans 則 break

    
    這樣 為什麼
    複雜度 OK呢??
    因為 ans是兩側的最短距
    代表說在兩側 斜邊長為ans的正方形
    內部只會有一個點
    而 q 又要滿足 與p y值差 < ans
    且 y座標在 [mid, mid+ans] 間
    根據鴿籠原理 對於每個p
    只會枚舉到 常數個q   
*/
// https://vijos.org/p/1012
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>

using namespace std;

#define INF 1e12

typedef pair<double, double> xy;
#define x first
#define y second

int N;
xy pt[200000];

bool cmp(int a, int b)
{
    return pt[a].y < pt[b].y;
}

double dis(int a, int b)
{
    double dx = pt[a].x-pt[b].x;
    double dy = pt[a].y-pt[b].y;

    return sqrt(dx*dx+dy*dy);
}

double solve(int L, int R)
{
    if( L+1 == R ) return INF;

    int mid = (L+R)/2;
    double re = min(solve(L, mid), solve(mid, R));

    vector<int> v;

    for(int i = L; i < R; i++)
        if( abs(pt[i].x-pt[mid].x) < re )
            v.push_back(i);

    sort(v.begin(), v.end(), cmp);

    for(int vi = 0; vi < v.size(); vi++)
        for(int vj = vi+1; vj < v.size(); vj++)
        {
            int i = v[vi], j = v[vj];

            if( abs(pt[i].y-pt[j].y) > re ) break;
            re = min(re, dis(i, j));
        }

    return re;
}

int main()
{
    scanf("%d", &N);

    for(int Ni = 0; Ni < N; Ni++)
        scanf("%lf %lf", &pt[Ni].x, &pt[Ni].y);

    sort(pt, pt+N);

    printf("%.3f\n", solve(0, N));
}

沒有留言:

張貼留言