Cod sursa(job #2054510)

Utilizator CroitoruAlinCroitoru Alin CroitoruAlin Data 2 noiembrie 2017 00:32:42
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.82 kb
#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <climits>
#include <cmath>
using namespace std;


struct punct
{
    int x,y;
};
class cmpx{
    public:
bool operator ()(const punct &a, const punct &b)
{
    return a.x<b.x;
}
};
class cmpy{
    public:
bool operator ()(const punct &a, const punct &b)
{
    return a.y<b.y;
}
};
long long dist(const punct& a, const punct& b)
{

    return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}

long long calculeaza(int p,int q,vector<punct> pct)
{
    long long d=LLONG_MAX;
    long long d1;
    for(int i=p;i<q;i++)
    {
        for(int j=i+1;j<=q;j++)
        {
            d1=dist(pct[i],pct[j]);
            if(d1<d)
                d=d1;
        }
    }
    return d;
}

vector<punct> aux;
long long solve(int p,int q,vector<punct> pct)
{
    if(q-p<3)
        return calculeaza(p,q,pct);

    int m=(p+q)/2;
    long long d1=solve(p,m,pct);
    long long d2=solve(m,q,pct);
    long long d=min(d1,d2);
    int i,j;
    aux.clear();
    for(i=p;i<q;i++)
        if((pct[i].x-pct[m].x)*(pct[i].x-pct[m].x)<d)
            aux.push_back(pct[i]);
    cmpy c2;
    sort(aux.begin(),aux.end(),c2);
    for(i=0;i<aux.size()-1;i++)
        for(j=i+1;(aux[j].y-aux[i].y)*(aux[j].y-aux[i].y)<d && j<aux.size();j++)
            if(d<dist(aux[i],aux[j]))
                d=dist(aux[i],aux[j]);

    return d;
}

int main()
{
    int n, i;
    ifstream fin("cmap.in");
    ofstream fout("cmap.out");
    fin >> n;
    vector<punct> p;
    punct aux;
    for(i=0;i<n;i++)
    {
        fin>>aux.x>>aux.y;
        p.push_back(aux);
    }
    cmpx c;
    sort(p.begin(),p.end(),c);
    long long d=solve(0,n-1,p);
        fout<<fixed<<setprecision(6)<<sqrt(d);
    return 0;
}