Cod sursa(job #2492164)

Utilizator andrei.busuiocAndrei Busuioc andrei.busuioc Data 14 noiembrie 2019 02:02:52
Problema Cele mai apropiate puncte din plan Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.76 kb
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <cmath>
#include <climits>
#include <fstream>

using namespace std;

struct punct{
    long long int x,y;
    int id;
};

vector <punct> P;


long long length(punct a,punct b){
    long long rv;
    rv=( 1LL*(a.x-b.x)*(a.x-b.x) + 1LL*(a.y-b.y)*(a.y-b.y) );
    return rv;
}

bool cmpP(punct a,punct b){
    if(a.x!=b.x)
        return a.x<b.x;
    else
        return a.y<b.y;
}

bool cmpPY(punct a,punct b){
    if(a.y!=b.y)
        return a.y<b.y;
    else
        return a.x<b.x;
}

long long rec(int s,int d){
//    double a,b;
//    int mid=(d-s)/2;
//    if(mid - s>2)
//        a=rec(P,s,mid);
//    else{
//        if(mid - s==2)
//            return min(length(P[s],P[mid-1]) , length(P[mid-1],P[mid]));
//        else
//            return length(P[s],P[mid]);
//    }
//    if (d-(mid + 1)>2)
//        b=rec(P,mid + 1,d);
//    else{
//        if(d-(mid + 1)==2)
//            return min(length(P[mid+1],P[d-1]) , length(P[d-1],P[d]));
//        else
//            return length(P[mid+1],P[d]);
//    }
//    double r=min(a,b);
    if(d-s<2)
        return INT_MAX;
    if(d-s==2)
        return length(P[d],P[s]);
    int mid=(s+d)/2;
    long long r=min(rec(s,mid),rec(mid,d));
    //cout<<sqrt(r)<<endl;
    if(d-s>2){
        vector <punct> Y;
        punct aux;
        long long x;
        for(int i=s;i<d;i++){
            aux.x=P[mid].x;
            aux.y=P[i].y;
            x=length(P[i],aux);
            if(x<r)
                Y.push_back(P[i]);
        }
        sort(Y.begin(),Y.end(),cmpPY);
        long long MIN=r;
        for(int i=0;i<Y.size()-1;i++){
            for(int j=i+1;j<=i+7 && j<Y.size();j++){
                x=length(Y[i],Y[j]);
                //cout<<"test";
                if(x<MIN)
                    MIN=x;
            }
        }
        //cout<<sqrt(MIN)<<endl<<endl;
        return MIN;
    }
    else
        return r;
}


int main()
{
    ifstream in("cmap.in");
    ofstream out("cmap.out");
    int n;
    in>>n;
    punct aux;
    for(int i=1;i<=n;i++){
        in>>aux.x>>aux.y;
        aux.id=i;
        P.push_back(aux);
    }
    sort(P.begin(),P.end(),cmpP);
    int s=0,d=n-1;
    long long r=rec(s,d);
//
//    for(int i=0;i<n;i++){
//        aux.x=midLine;
//        aux.y=P[i].y;
//        x=length(P[i],aux);
//        if(x<=r)
//            Y.push_back(P[i]);
//    }
//    double MIN=INT_MAX;
//    for(int i=0;i<Y.size()-1;i++){
//        for(int j=i+1;j<i+7 && j<Y.size();j++){
//            x=length(Y[i],Y[j]);
//            if(x<MIN)
//                MIN=x;
//        }
//    }
    out<<setprecision(8)<<sqrt(r);

    return 0;
}