Cod sursa(job #2492512)

Utilizator Natasa_CNatasa Cirstea Natasa_C Data 14 noiembrie 2019 20:45:31
Problema Cele mai apropiate puncte din plan Scor 85
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.28 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <utility>
#include <bits/stdc++.h>
#include <math.h>
#include<climits>
using namespace std;

long long get_dist(pair<long long, long long> a, pair<long long, long long> b)
{
    return (a.first - b.first)*(a.first - b.first) + (a.second - b.second)*(a.second - b.second);
}


long long distanta(int n, vector<pair<long long, long long>> x)
{
    int i,j;

    if(n<=3)
    {
        long long dist = LLONG_MAX;

        for( i=0; i<=n-2; i++)
            for(j=i+1; j<=n-1; j++)
            {
                long long d_puncte = get_dist(x[i], x[j]);
                dist = min(dist, d_puncte);
            }

        return dist;
    }
    else
    {
        int middle = n/2;
        vector<pair<long long, long long>> xs;
        vector<pair<long long, long long>> xd;
        vector<pair<long long, long long>> band;

        for(i=0; i<=middle; i++)
            xs.push_back(x[i]);

        for(i=middle+1; i<n; i++)
            xd.push_back(x[i]);

        long long ds, dd, d;

        ds = distanta((int)xs.size(), xs);
        dd = distanta((int)xd.size(), xd);

        d = min(dd, ds);

        for(i=0; i<n; i++)
            if(x[i].first>=(x[middle].first-d) && x[i].first<=(x[middle].first + d))
                band.push_back(make_pair(x[i].second, x[i].first));

        sort(band.begin(), band.end());

        for(i=0; i<(int)band.size()-7; i++)
            for( j=i+1; j<=i+7; j++)
            {
                long long dist = get_dist(band[i], band[j]);
                d = min(d, dist);
            }

        return d;
    }
}

int main()
{
    int n, i;
    long long a, b, dmin;

    ifstream inFile;
    inFile.open("cmap.in");
    if (!inFile)
    {
        cout << "Unable to open file";
        exit(1); // terminate with error
    }

    inFile >> n;
    vector<pair<long long, long long>> x;

    for (i = 0; i < n; i++)
    {
        inFile >> a >> b;
        x.push_back(make_pair(a, b));
    }
    inFile.close();

    sort(x.begin(), x.end());

    dmin = distanta(n, x);

    ofstream outFile;

    outFile.open("cmap.out");
    if (!outFile)
    {
        cout << "Unable to open file";
        exit(1); // terminate with error
    }

    outFile<<fixed<<setprecision(6)<<sqrt((double)dmin);

    outFile.close();

    return 0;
}