Cod sursa(job #2049112)

Utilizator zanugMatyas Gergely zanug Data 26 octombrie 2017 21:10:04
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.1 kb
#include <iostream>
#include <fstream>
#include <cmath>
#include <cstdlib>
#include <vector>

#define ld long double
#define pb push_back

using namespace std;

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

const int N = 1e5 + 10;

struct point
{
    int x, y;
};

int compx(const void* a, const void* b)
{
    point x = *(point*)a;
    point y = *(point*)b;

    if(x.x - y.x == 0)
        return x.y - y.y;
    return x.x - y.x;
}

int compy(const void* a, const void* b)
{
    point x = *(point*)a;
    point y = *(point*)b;

    if(x.y - y.y == 0)
        return x.x - y.x;
    return x.y - y.y;
}

int n;
point p[N];
ld mini = 4e9;

ld points3(int l, int r)
{
    vector < ld > dis;
    dis.pb(sqrt((p[l].x - p[r].x) * (p[l].x - p[r].x) + (p[l].y - p[r].y) * (p[l].y - p[r].y)));
    int i = 1;
    while(l++ < r)
    {
        dis.pb(sqrt((p[l].x - p[l+1].x) * (p[l].x - p[l+1].x) + (p[l].y - p[l+1].y) * (p[l].y - p[l+1].y)));
    }
    ld minid = min(dis[0], dis[1]);
    if(dis.size() == 2) return minid;
    else return min(minid, dis[3]);

}

ld solve(int l, int r)
{
    if(l + 4 > r)
        return points3(l, r);

    int mid = (l + r)/2;

    mini = min(mini, min(solve(l, mid), solve(mid+1, r)));

    for(int i = 0; i < n; ++i)///!
    {
        for(int j = i; j < n && p[j].y - p[i].y < mini; ++j)
        {
            for(int ii = i; ii < j; ++i)
            {
                ld mini2 = sqrt((p[ii].x - p[j].x) * (p[ii].x - p[j].x) + (p[ii].y - p[j].y) * (p[ii].y - p[j].y));
                mini = min(mini, mini2);
            }
        }
    }

    return mini;
}

int main()
{
    //ios::sync_with_stdio(false);

    fin >> n;

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

    for(int i = 0; i < n; ++i)
    {
        cout << p[i].x << " " << p[i].y << "\n";
    }

    qsort(p, n, sizeof(p), compx);

    for(int i = 0; i < n; ++i)
    {
        cout << p[i].x << " " << p[i].y << "\n";
    }

    ld mindist = solve(0, n-1);

    cout << mindist << "\n";


    return 0;
}