Cod sursa(job #1813170)

Utilizator Y0da1NUME JMECHER Y0da1 Data 22 noiembrie 2016 19:21:43
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.01 kb
#include <iostream>
#include <algorithm>
#include <vector>
#include <fstream>
#include <iomanip>
using namespace std;
class punct{
public:
    int64_t x;
    int64_t y;

    bool operator <(const punct p2) const
    {
        if(x<p2.x)
        return 1;
    else
        if(x>p2.x)
            return 0;
    if(y<p2.y) //daca au abscisele egale sortam dupa y
        return 1;
    return 0;
    }
};

float compareY(const punct a, const punct b)
{
    return (a.y < b.y);
}

punct v[100005];
int N;

float pldist(punct p1, punct p2)
{
    return sqrt( (p1.x - p2.x)*(p1.x - p2.x) +
                 (p1.y - p2.y)*(p1.y - p2.y)  );
}

float brutu(punct p[], int n)
{
    float minim = 2e9;
    for (int i = 0; i < n; ++i)
        for (int j = i+1; j < n; ++j)
            if (pldist(p[i], p[j]) < minim)
                minim = pldist(p[i], p[j]);
    return minim;
}
float minfasie(punct fasie[], int sz, float dist)
{
    float minim = dist;
    sort(fasie, fasie+sz, compareY);
    for (int i = 0; i < sz; ++i)
        for (int j = i+1; j < sz && (fasie[j].y - fasie[i].y) < minim; ++j)
            if (pldist(fasie[i],fasie[j]) < minim)
                minim = pldist(fasie[i], fasie[j]);

    return minim;
}
float div_and_q(punct p[], int n)
{
    if(n<4)
        return brutu(p, n);
    int mid = n/2;
    punct mijloc = p[mid]; //puncti prin care ducem o || la Oy
    float dl = div_and_q(p, mid);
    float dr = div_and_q(p + mid, n-mid);
    float dist = min(dl, dr);
    punct fasie [n];
    int j = 0;
    for (int i = 0; i < n; i++)
        if (abs(p[i].x - mijloc.x) < dist)
        {
            fasie[j] = p[i];
            ++j;
        }
    return min(dist, minfasie(fasie, j, dist));
}

int main()
{

    ifstream in ("cmap.in");
    ofstream out ("cmap.out");
    int i;
    in>>N;
    for(i=0;i<N;++i)
        in>>v[i].x>>v[i].y;
    sort(v, v+N);
    out<<fixed<<setprecision(6)<<div_and_q(v, N);
    in.close();
    out.close();
    return 0;
}