Morris' Blog 我在摸索我存在的意義、生命的意義、內涵及價值。 沒有真正神手般的厲害，套用模式是大部分的情況。 沒那麼厲害的我存在的意義為何，襯托出神的存在？ 有時候不能怪別人不給我機會，我已經開始省思， 為什麼我沒有給別人機會的原因，而是全要靠別人。 有時候我認為我與眾不同，那是因為我做不到很多人能辦到的事情。 我聽不到、玩不起來、說得不夠明瞭、理解得不夠多， 我缺少的語文能力，就是一切一切無能的判定。 為此，我不曉得能做些對別人有幫助的事情。 我知道我自己是個不服輸的性格，但現在我不得不認輸。 我沒有能力，因此我必須認輸。 我到底來這世界作什麼？處處充滿不確定性， 而我總是無法出類拔萃，想當個一般人似乎也回不了頭了。 越強大的挑戰需要越強力的支持，而我的支持是什麼？ 最近嘗試與人談話，但都是失敗的結局，沒人能接受， 不需要言語，不需要溝通，一切所想都表達不出來。

49愛的鼓勵 6訂閱站台

內容 ：

輸入說明 ：

輸出說明 ：

範例輸入 ：

範例輸出 ：

提示 ：

出處 ：

/*****************************************************************/
/*  Problem: a638 "Closest-pair problem" from                    */
/*  Language: CPP (1951 Bytes)                                   */
/*  Result: AC(108ms, 10.4MB) judge by this@ZeroJudge            */
/*  Author: morris1028 at 2013-03-11 12:58:31                    */
/*****************************************************************/


#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define oo 100000000
typedef struct {
    float x, y;
}Point;
Point D[3000000];
int cmp(const void *i, const void *j) {
    Point *x, *y;
    x = (Point *)i, y = (Point *)j;
    if(x->x != y->x)
        return x->x - y->x < 0 ? 1 : -1;
    return x->y - y->y < 0 ? 1 : -1;
}
double Min(double x, double y) {
    return x < y ? x : y;
}
double Merge(int l, int m, int r, double d) {
    double midL = D[m].x;
    int i, j;
    for(i = m; i >= l; i--) {
        if((D[i].x-midL)*(D[i].x-midL) >= d)    break;
        for(j = m+1; j <= r; j++) {
            if((D[i].x-D[j].x)*(D[i].x-D[j].x) >= d)    break;
            d = Min(d, (D[i].x-D[j].x)*(D[i].x-D[j].x)+(D[i].y-D[j].y)*(D[i].y-D[j].y));
        }
    }
    return d;
}
double ClosestPair(int l, int r, double *dis) {
    if(l < r) {
        if(l == r-1) {
            return (D[l].x-D[r].x)*(D[l].x-D[r].x) + (D[l].y-D[r].y)*(D[l].y-D[r].y);
        }
        int m = (l+r)>>1;
        *dis = Min(*dis, ClosestPair(l, m, dis));
        *dis = Min(*dis, ClosestPair(m+1, r, dis));
        *dis = Min(*dis, Merge(l, m, r, *dis));
        return *dis;
    }
    return oo;
}
inline int readchar() {
    const int N = 1048576;
    static char buf[N];
    static char *p = buf, *end = buf;
    if(p == end) {
        if((end = buf + fread(buf, 1, N, stdin)) == buf) return EOF;
        p = buf;
    }
    return *p++;
}
inline int ReadInt(int *x) {
    static char c, neg;
    while((c = readchar()) < '-')    {if(c == EOF) return 0;}
    neg = (c == '-') ? -1 : 1;
    *x = (neg == 1) ? c-'0' : 0;
    while((c = readchar()) >= '0')
        *x = (*x << 3) + (*x << 1) + c-'0';
    *x *= neg;
    return 1;
}
int main() {
    int N, i, x, y;
    ReadInt(&N);
    for(i = 0; i < N; i++) {
        ReadInt(&x), ReadInt(&y);
        D[i].x = x, D[i].y = y;
    }
    double distance = oo;
    distance = ClosestPair(0, N-1, &distance);
    distance = sqrt(distance);
    printf("%.4lf\n", distance);
    return 0;
}