Cod sursa(job #1820393)

Utilizator Y0da1NUME JMECHER Y0da1 Data 1 decembrie 2016 17:33:24
Problema Cele mai apropiate puncte din plan Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 3.7 kb
#include <iostream>
#include <algorithm>
#include <vector>
#include <fstream>
#include <iomanip>
#include <math.h>
#define i64 unsigned long long
#define INF 2000000000
#define MAXN 100010
#define BUFF_SIZE 1048576
using namespace std;

class punct{
public:
    i64 x;
    i64 y;

    bool operator <(const punct p2) const
    {
        return x < p2.x;
    }
};
class InParser {
private:
    FILE *fin;
    char *buff;
    int sp;

    char read_ch()
    {
        ++sp;
        if (sp == BUFF_SIZE) {
            sp = 0;
            fread(buff, 1, BUFF_SIZE, fin);
        }
        return buff[sp];
    }
public:
    InParser(const char* nume)
    {
        fin = fopen(nume, "r");
        buff = new char[BUFF_SIZE]();
        sp = BUFF_SIZE-1;
    }
    InParser& operator >> (int &n) {
        char c;
        while (!isdigit(c = read_ch()) && c != '-');
        int sgn = 1;
        if (c == '-') {
            n = 0;
            sgn = -1;
        } else {
            n = c - '0';
        }
        while (isdigit(c = read_ch())) {
            n = 10 * n + c - '0';
        }
        n *= sgn;
        return *this;
    }
    InParser& operator >> (unsigned long long &n)
    {
        char c;
        n = 0;
        while (!isdigit(c = read_ch()) && c != '-');
        long long sgn = 1;
        if (c == '-') {
            n = 0;
            sgn = -1;
        } else {
            n = c - '0';
        }
        while (isdigit(c = read_ch())) {
            n = 10 * n + c - '0';
        }
        n *= sgn;
        return *this;
    }
};
i64 compareY(const punct a, const punct b)
{
    return (a.y < b.y);
}

punct X[100005], Y[100005];
int N;
i64 last;
i64 pldist(punct p1, punct p2)
{
    return /*sqrt*/( (p1.x - p2.x)*(p1.x - p2.x) +
                 (p1.y - p2.y)*(p1.y - p2.y)  );
}

i64 brutu(punct p[], int n)
{
    i64 minim = 4e18;
    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;
}
i64 minfasie(punct fasie[], int sz, i64 dist)
{
    i64 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;
}
i64 div_and_q(int st, int dre, punct x[], punct y[])
{
    if(dre-st<3)
        return brutu(x, dre-st);
    int mid = (st+dre)/2;
    punct mijloc = x[mid]; //puncte prin care ducem o || la Oy
    //punct yl[dre-st+1];   // y stanga
    //punct yr[dre-st+1];  // y dreapta
    int li=0, ri=0;
    /*for (int i = 0; i < dre-st; i++)
    {
      if (y[i].x <= mijloc.x)
      {
         yl[li] = y[i];
         ++li;
      }
      else
      {
         yr[ri] = y[i];
         ++ri;
      }
    }*/
    i64 dl = div_and_q(st, mid, x, y);
    i64 dr = div_and_q(mid, dre, x, y);
    i64 dist = min(dl, dr);
    //cout<<dist<<"\n";
    sort(y + st, y + dre, compareY);
    punct fasie [dre-st];
    int j = 0;
    for (int i = st; i < dre; ++i)
        if (abs(y[i].x - mijloc.x) < dist)
        {
            fasie[j] = y[i];
            ++j;
        }
    return min(dist, minfasie(fasie, j, dist));
}

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