Cod sursa(job #2464739)

Utilizator CosminMorarMorar Cosmin Andrei CosminMorar Data 28 septembrie 2019 21:02:12
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.5 kb
#include <iostream>
#include <fstream>
#include <cmath>
#include <iomanip>
#include<bits/stdc++.h>
using namespace std;
ifstream f("cmap.in");
ofstream g("cmap.out");
#define MAX_SIZE 100001
int n, i, j, pos;
double dpos;
double dist, dmin;
struct Punct {
    int x, y;
} punct[MAX_SIZE], fpunct[MAX_SIZE], w[MAX_SIZE];

double Dist(int i, int j) {
    return sqrt((punct[i].x-punct[j].x)*(punct[i].x-punct[j].x) + (punct[i].y-punct[j].y)*(punct[i].y-punct[j].y));
}

double fDist(int i, int j) {
    return sqrt((fpunct[i].x-fpunct[j].x)*(fpunct[i].x-fpunct[j].x) + (fpunct[i].y-fpunct[j].y)*(fpunct[i].y-fpunct[j].y));
}

void msort(int st,int m,int dr)
{
    int i=st,j=m+1,k=st-1;
    for(; i<=m&&j<=dr;)
    {
        if(punct[i].y<punct[j].y){
            w[++k]=punct[i++];
        }
        else
            w[++k]=punct[j++];
    }
    while(i<=m){
        w[++k]=punct[i++];
    }
    while(j<=dr){
        w[++k]=punct[j++];
    }
    for(i=st;i<=dr;i++)
        punct[i]=w[i];
}

void fmsort(int st,int m,int dr)
{
    int i=st,j=m+1,k=st-1;
    for(; i<=m&&j<=dr;)
    {
        if(fpunct[i].y<fpunct[j].y){
            w[++k]=fpunct[i++];
        }
        else
            w[++k]=fpunct[j++];
    }
    while(i<=m){
        w[++k]=fpunct[i++];
    }
    while(j<=dr){
        w[++k]=fpunct[j++];
    }
    for(i=st;i<=dr;i++)
        fpunct[i]=w[i];
}


double Recursivitate(int in, int sf) {
    int dif = sf-in+1;
    int sum = sf+in;
    if(dif > 255) {
        dmin = min(Recursivitate(in, sum/2), Recursivitate(sum/2+1, sf));
        if(dif%2 == 1)
            dpos = double(punct[in+dif/2+1].x);
        else dpos = double(punct[in+dif/2].x + punct[in+dif+1].x)/2;

        pos = 0;
        for(i = in; i <= sf; i++) {
            if(abs(punct[i].x - dpos) < dmin) {
                fpunct[++pos] = punct[i];
            }
        }
        fmsort(in, in+dif/2, sf);

        for(i = 1; i < pos; i++) {
            for(j = i+1; j <= i+7 && j <= pos; j++) {
                dmin = min(dmin, fDist(i, j));
            }
        }
    }
    else {
        dmin = LONG_MAX;
        for(i = in; i < sf; i++)
            for(j = i+1; j <= sf; j++)
                dmin = min(dmin, Dist(i, j));
    }
    return dmin;
}

int main()
{
    dmin = LONG_MAX;
    f >> n;
    for(i = 1; i <= n; i++)
        f >> punct[i].x >> punct[i].y;

    msort(1, n/2, n);

    g << fixed << setprecision(6) << Recursivitate(1, n);
    return 0;
}