Cod sursa(job #1890261)

Utilizator tudorgalatanRoman Tudor tudorgalatan Data 23 februarie 2017 10:33:04
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.71 kb
#include <fstream>
#include <algorithm>
#include <cmath>
#include <iomanip>

using namespace std;

ifstream fin ("cmap.in");
ofstream fout ("cmap.out");

struct point
{
    int x, y;
};

bool compare (point a, point b);
long double dist (point a, point b);

unsigned int n;
point v[100001];

long double w;
unsigned int i;
int j;

long double sol;

int main ()
{
    /// READ
    fin >> n;
    for (i=1; i<=n; i++)
        fin >> v[i].x >> v[i].y;                    /// Store points by their coordinates.

    /// SOLVE
    sort(v+1,v+n+1,compare);                        /// Sort the points.
    sol = dist(v[1],v[2]);                          /// Initialize solution.
    for (i=3; i<=n; i++)                            /// Continue to calculate the best solution.
    {
        j = i - 1;                                  /// We start from a previous position.
        while (v[i].x-v[j].x < sol && j >= 1)
        {
            w = dist(v[i],v[j]);                    /// Calculate the distance between those points.
            if (w < sol)                            /// If we have a smaller distance...
                sol = w;                            /// Update the solution.
            j -= 1;                                 /// Continue to check.
        }
    }

    /// PRINT
    fout << fixed << setprecision(6) << sol;
    return 0;
}

bool compare (point a, point b)     /// A function that helps as sort the points by their X coordinates.
{
    if (a.x < b.x)
        return 1;
    return 0;
}

long double dist (point a, point b)      /// A function that calculates the distance between two points.
{
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}