Cod sursa(job #1542166)

Utilizator Liviu0010Oprescu Liviu Liviu0010 Data 5 decembrie 2015 03:29:20
Problema Cele mai apropiate puncte din plan Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 2.71 kb
#include<fstream>
#include<iostream>
#include<cmath>
#include<limits>
using namespace std;

class Punct
{
public:
    long long x, y;

    Punct(long long x, long long y)
    {
        this->x = x;
        this->y = y;
    }

    Punct()
    {
        x = y = 0;
    }

    long long distance(Punct p)
    {
        return (x-p.x)*(x-p.x) + (y-p.y)*(y-p.y);
    }
} *P;

long long getMin(int start, int end, Punct ySorted[])
{
    long long minSt, minDr, minD;

    if(end - start <= 2)
    {
        minD = P[start].distance(P[start+1]);

        for(int i = start; i < end; i++)
            for(int j = i+1; j<= end; j++)
                if(P[i].distance(P[j]) < minD)
                    minD = P[i].distance(P[j]);

        for(int i = start; i<= end; i++)
               ySorted[i] = P[i];

        for(int i = start; i < end; i++)
        {
            int min = i;
            Punct aux;

            for(int j = i+1; j <= end; j++)
                if(ySorted[min].y > ySorted[j].y)
                    min = j;

            if(min != i)
            {
                aux = ySorted[i];
                ySorted[i] = ySorted[min];
                ySorted[min] = aux;
            }
        }

        return minD;
    }

    minSt = getMin(start, (start + end)/2, ySorted);
    minDr = getMin((start + end)/2+1, end, ySorted);

    minD = minSt < minDr ? minSt : minDr;

    int a = start, b = (start+end)/2+1, ntmp = 0;
    Punct *tmp = new Punct[end-start+1];

    while(a <= (start+end)/2 && b <= end)
        if(ySorted[a].y < ySorted[b].y)
            tmp[ntmp++] = ySorted[a++];
        else
            tmp[ntmp++] = ySorted[b++];

    while(a <= (start+end)/2)
        tmp[ntmp++] = ySorted[a++];

    while(b <= end)
        tmp[ntmp++] = ySorted[b++];

    for(int i = 0; i < ntmp; i++)
        ySorted[i+start] = tmp[i];

    Punct *db = new Punct[ntmp];
    int ndb = 0;

    for(int i = start; i <= end; i++)
        if(abs(ySorted[i].x - P[(start+end)/2].x) <= minD)
            db[ndb++] = ySorted[i];

    for(int i = 0; i < ndb; i++)
        for(int j = i+1; j < ndb && j <= i + 7; j++)
            if(db[i].distance(db[j]) < minD)
                minD = db[i].distance(db[j]);
    delete db;
    delete tmp;

    return minD;
}

int main()
{
    int n;
    long a, b;
    Punct *s;
    fstream in("cmap.in", ios::in), out("cmap.out", ios::out);

    in>>n;

    P = new Punct[n];
    s = new Punct[n];

    for(int i = 0; i < n; i++)
    {
        in>>a;
        in>>b;
        P[i] = Punct(a,b);
    }

    in.close();

    out<<fixed<<sqrt(getMin(0, n-1, s));
    out.close();

    delete P;
    delete s;

    return 0;
}