Cod sursa(job #1026914)

Utilizator R.A.RFMI Romila Remus Arthur R.A.R Data 12 noiembrie 2013 10:40:49
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.97 kb
#include <fstream>
#include <cmath>
#include <iomanip>
using namespace std;

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

const int NMAX = 100002;

int minDist = NMAX;

int N;

class point{
public:

    int x,y;
    bool operator <(const point &b){
        if(x == b.x){
            return y < b.y;
        }
        else {
            return x < b.x;
        }
    }
}V[NMAX];

int distancePoints(const point &a, const point&b){
    return (a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y);
}

void swap(point &a, point &b){
    point c = a;
    a = b;
    b = c;
}

void merge(int firstI,int lastI,int firstJ,int lastJ){
    int N = lastI - firstI + 1;
    int M = lastJ - firstJ + 1;
    int i,j,k;
    point X[N+1];
    point Y[M+1];
    for(i = 0; i < N; i++)
        X[i] = V[firstI + i];
    for(i = 0; i < M; i++)
        Y[i] = V[firstJ + i];
    X[N].x = X[N].y = Y[M].x = Y[M].y = (1<<30);

    for(i = 0, j = 0, k = 0; i < N || j < M;k++){
        if(X[i] < Y[j]){
            V[firstI + k] = X[i];
            i++;
        }
        else {
            V[firstI + k] = Y[j];
            j++;
        }
    }
}

int conquer(int first, int last){
    if(last - first < 3){
        if(last - first == 2){
            if(V[first] < V[first+1] && V[first] < V[first+2]){
                if(V[first+2] < V[first+1])
                    swap(V[first+2],V[first+1]);
            }
            else if(V[first+1] < V[first] && V[first + 1]<V[first+2]){
                swap(V[first], V[first+1]);
                if(V[first+2] < V[first+1])
                    swap(V[first+2],V[first+1]);
            }
            else if(V[first + 2] < V[first] && V[first+2] < V[first+1]){
                swap(V[first],V[first+2]);
                if(V[first+2] < V[first+1])
                    swap(V[first+2],V[first+1]);
            }
            int d1 = distancePoints(V[first],V[first+1]);
            int d2 = distancePoints(V[first],V[first+2]);
            int d3 = distancePoints(V[first+1],V[last]);

            return min(min(d1,d2),d3);
        }
        if(last - first == 1){
            if(V[first + 1] < V[first])
                swap(V[first], V[last]);
            return distancePoints(V[first],V[last]);
        }

        return 0;
    }
    else {
        int middle = (first + last)/2;
        int min1 = conquer(first, middle);
        int min2 = conquer(middle+1,last);
        //interclasez
        merge(first,middle,middle+1,last);

        minDist = min(minDist,min(min1,min2));

        for(int i=first; i <= last; i++){
            for(int j = i+1; j <=last && j - i < 8; j++){
                minDist = min(minDist, distancePoints(V[i],V[j]));
            }
        }

        return minDist;
    }
}

int main()
{

    int i;
    in >> N;

    for(i = 0; i < N; i++){
        in >> V[i].x >> V[i].y;
    }

    out << conquer(0,N-1);

    out<<setprecision(20)<<sqrt(minDist);
    return 0;
}