Cod sursa(job #2731826)

Utilizator andi1010Brinceanu Andi andi1010 Data 28 martie 2021 13:26:57
Problema Cele mai apropiate puncte din plan Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.99 kb
#include<iostream>
#include<fstream>
#include<math.h>
#include<algorithm>
#include<iomanip>
using namespace std;

ifstream fin ("cmap.in");
ofstream fout ("cmap.out");
struct punct
{
    int x, y;
};

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

void mergesortX(punct v[], int st, int dr)
{
    if(st == dr)
        return;
    int mid = (st + dr) / 2;
    mergesortX(v, st, mid);
    mergesortX(v, mid+1, dr);

    struct punct t[dr-st+1];
    int k=0;
    int i=st, j=mid+1;
    while(i<=mid && j<=dr)
    {
        if(v[i].x < v[j].x)
        {
            t[k++]=v[i++];
        }
        else
        {
            t[k++]=v[j++];
        }
    }
    while(i<=mid)
    {
        t[k++]=v[i++];
    }
    while(j<=dr)
    {
        t[k++]=v[j++];
    }
    for(int p=st; p<=dr; p++)
    {
        v[p]=t[p-st];
    }
}

void mergesortY(punct v[], int st, int dr)
{
    if(st == dr)
        return;
    int mid = (st + dr) / 2;
    mergesortY(v, st, mid);
    mergesortY(v, mid+1, dr);

    struct punct t[dr-st+1];
    int k=0;
    int i=st, j=mid+1;
    while(i<=mid && j<=dr)
    {
        if(v[i].y < v[j].y)
        {
            t[k++]=v[i++];
        }
        else
        {
            t[k++]=v[j++];
        }
    }
    while(i<=mid)
    {
        t[k++]=v[i++];
    }
    while(j<=dr)
    {
        t[k++]=v[j++];
    }
    for(int p=st; p<=dr; p++)
    {
        v[p]=t[p-st];
    }
}

double sol1(punct v[], int n)  //pentru 2 sau 3 puncte
{
    double dmin = 100000;
    for(int i = 0; i < n; i++)
        for(int j = i + 1; j < n; j++)
            if(distanta(v[i], v[j]) < dmin)
                dmin = distanta(v[i], v[j]);
    return dmin;
}

double cmap(punct vx[], punct vy[], int n)
{
    if(n <= 3)
        return sol1(vx, n);
    int mij = n / 2;
    punct pst[mij];
    punct psd[n - mij];
    int st = 0, dr = 0;
    for(int i = 0; i < n; i++)
    {
        if(vy[i].x <= vx[mij].x)
            pst[st++] = vy[i];
        else
            psd[dr++] = vy[i];
    }

    double left = cmap(vx, pst, mij);
    double right = cmap(vx + mij, psd, n - mij);
    double d = min(left, right);

    punct utile[n];
    int m = 0;
    for(int i = 0; i < n; i++)
        if(abs(vy[i].x - vx[mij].x) < d)
        {
            utile[m] = vy[i];
            m++;
        }

    for(int i = 0; i < m; i++)
        for(int j = i + 1; j < m && j < i + 8; j++)
            if(distanta(utile[i], utile[j]) < d)
                d = distanta(utile[i], utile[j]);
    return d;
}


int main()
{
    punct vx[100000];
    punct vy[100000];
    int n;
    fin >> n;
    for(int i = 0; i < n; i++)
        fin >> vx[i].x >> vx[i].y;
    for(int i = 0; i < n; i++)
        vy[i] = vx[i];
    mergesortX(vx, 0, n - 1);
    mergesortY(vy, 0, n - 1);
    fout << fixed << setprecision(8);
    fout << cmap(vx, vy, n);

    return 0;
}