Cod sursa(job #2464699)

Utilizator CosminMorarMorar Cosmin Andrei CosminMorar Data 28 septembrie 2019 20:02:43
Problema Cele mai apropiate puncte din plan Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.94 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, rez;
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 FindMinDist(int in, int sf) {
    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]);
            }
        }
    }


    if(n <= 3)
        for(i = 1; i < n; i++)
            for(j = i+1; j <= n; j++)
                dmin = min(rez, Dist(i, j));
    else {
        dmin = min(FindMinDist(1, n/2), FindMinDist(n/2+1, n));
        if(n%2 == 1)
            dpos = double(punct[n/2+1].x);
        else dpos = double(punct[n/2].x + punct[n/2+1].x)/2;

        for(i = 1; i <= n; 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++) {
                dmin = min(dmin, fDist(i, j));
            }
        }
    }
    g << fixed << setprecision(6) << dmin;
    return 0;
}