Cod sursa(job #2464745)

Utilizator CosminMorarMorar Cosmin Andrei CosminMorar Data 28 septembrie 2019 21:13:01
Problema Cele mai apropiate puncte din plan Scor 15
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.84 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];

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

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

double Recursivitate(int in, int sf) {
    int dif = sf-in+1;
    int sum = sf+in;
    if(dif > 3) {
        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];

        for(i = 1; i < pos; i++)
            for(j = i+1; j <= pos; j++)
                if(fpunct[i].y > fpunct[j].y)
                    swap(fpunct[i], fpunct[j]);

        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;

    for(i = 1; i < n; i++)
        for(j = i+1; j <= n; j++)
            if(punct[i].x > punct[j].x)
                swap(punct[i], punct[j]);

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