Cod sursa(job #1025623)

Utilizator IoannaPandele Ioana Ioanna Data 10 noiembrie 2013 12:57:39
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.74 kb
#include <fstream>
#include <iomanip>
#include <cmath>
#define epx 0.000001


using namespace std;

struct punct {
    int x,y;
};

punct p[100001], y[100001];
int n;

ifstream in("cmap.in");
ofstream out("cmap.out");

void read() {
    in>>n;
    for (int i = 0; i < n; i++) {
        in>>p[i].x>>p[i].y;
    }
}

int part(int st, int dr) {
    punct aux, pivot;
    int i, j;
    pivot = p[(st+dr)/2];
    i = st-1;
    j = dr+1;
    while (1) {
        do {i++;}while (p[i].x<pivot.x || (p[i].x == pivot.x && p[i].y < pivot.y));
        do {j--;}while (p[j].x>pivot.x || (p[j].x == pivot.x && p[j].y > pivot.y));
        if (i<j) {
            aux = p[i];
            p[i] = p[j];
            p[j] = aux;
        } else return j;
    }
}

void quicks(int st, int dr) {
    int p;
    if (st < dr){
    p = part(st, dr);
    quicks(st, p);
    quicks(p+1, dr);
    }
}

long long distanta(punct p1, punct p2) {
    return (long long) (p1.x - p2.x) * (p1.x - p2.x) + (long long) (p1.y - p2.y) * (p1.y - p2.y);
}

long long solve(int st, int dr) {
    if (dr - st + 1 == 3)
    {
        long long d1, d2, d3;

        int sortat;

        d1 = distanta(p[st], p[st+1]);
        d2 = distanta(p[st+1], p[dr]);
        d3 = distanta(p[dr], p[st]);
        do {
            sortat = 1;
            for (int i = st; i < dr; i++) {
                if (y[i].y > y[i+1].y) {
                    swap(y[i], y[i+1]);
                    sortat = 0;
                }
            }
        } while (!sortat);

        return min(d1,min(d2,d3));
    }
    if (dr - st + 1 == 2) {
        if (y[st].y > y[dr].y) {
            swap(y[st], y[dr]);
        }
        return distanta(p[st], p[dr]);


    }

    int mij = (st+dr)/2;

    long long dst, ddr, D;
    punct v[dr - st + 2];

    dst = solve(st, mij);
    ddr = solve(mij + 1, dr);
    D = min(dst, ddr);

    int k = 0, i, j;
    for (i = st, j = mij + 1; i <= mij && j <= dr;) {
        if (y[i].y < y[j].y) {
            v[++k] = y[i];
            i++;
        } else {
            v[++k] = y[j];
            j++;
        }
    }
    for (; i <= mij; i++){
        v[++k] = y[i];
    }

    for (; j <= dr; j++) {
        v[++k] = y[j];
    }

    for (i = 1; i <= k; ++i) {
        for (j = i + 1; j <= k && j < 7 + i ; ++j) {
            D = min(D, distanta(v[i], v[j]));
        }
    }

    for (i = st, j = 1; i <= dr; i++, j++) {
        y[i] = v[j];
    }
    return D;
}



int main() {
    read();
    quicks(0, n-1);

    for (int i = 0; i < n; i++) {
        y[i] = p[i];
    }

    long long D = solve(0,n-1);

    ofstream out("cmap.out");

    out<<setprecision(8)<<sqrt(D);

    return 0;

}