Cod sursa(job #2064836)

Utilizator d0rina2011Craciun Dorina d0rina2011 Data 12 noiembrie 2017 21:40:28
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.08 kb
#include <fstream>
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <math.h>
#include <stdlib.h>

using namespace std;

ifstream fin("cmap.in");
ofstream fout("cmap.out");

#define NMAX 100000

struct Punct{
    int x, y;
};

int sortx(Punct &A, Punct &B)
{
    return (A.x < B.x || (A.x == B. x && A.y < B.y));
}

int sorty(Punct &A, Punct &B)
{
    return A.y < B.y;
}

double sq_dist(const Punct &A, const Punct &B)
{
    return (A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y);
}

Punct P1, P2;

double cmap(int p, int u, vector<Punct> &px, vector<Punct> &py)
{

    if(p >= u)return NMAX;
    if(u - p == 1)
    {
        if(py[p].y > py[u].y)
            swap(py[p], py[u]);
        P1 = py[p];
        P2 = py[u];
        return sq_dist(py[p], py[u]);
    }
    int m = (p + u) / 2;
    double dmin_stg = cmap(p, m, px, py);
    double dmin_dr = cmap(m + 1, u, px, py);
    double dmin = min(dmin_stg, dmin_dr);
    vector<Punct> t(u - p + 1);
    merge(py.begin() + p, py.begin() + m + 1, py.begin() + m + 1, py.begin() + u + 1, t.begin(), sorty);
    copy(t.begin(), t.end(), py.begin() + p);

    int i, j;
    vector<Punct> w;

    for(i = p; i <= u; i++)
        if(abs(px[m].x - py[i].x) <= dmin)
            w.push_back(py[i]);

    for(i = 0; i < w.size(); i++)
    {
        for(j = i + 1; j < w.size() && j < i + 8; j++)
        {
            if(sq_dist(w[i], w[j]) < dmin)
            {
                dmin = sq_dist(w[i], w[j]);
                P1= w[i];
                P2 = w[j];
            }
        }
    }
    return dmin;
}

int main()
{
    int n;
    fin >> n;
    vector<Punct> px(n), py(n);
    int i;

    for(i = 0; i < n; i++)
    {
        fin >> px[i].x >> px[i].y;
        py[i].x = px[i].x;
        py[i].y = px[i].y;
    }

    sort(px.begin(), px.end(), sortx);

    float dmin = cmap(0, n - 1, px, py);
    fout << fixed << setprecision(6) << sqrt(dmin) << '\n';
    //fout << P1.x << " " << P1.y << '\n' << P2.x << " " << P2.y;
    return 0;
}