Cod sursa(job #2089109)

Utilizator cristii2000cristiiPanaite Cristian cristii2000cristii Data 16 decembrie 2017 10:57:26
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.47 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>
#define X first
#define Y second
#define Punct pair <long long, long long>

using namespace std;

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

Punct PointX[100010], PointY[100010];
Punct Distante[100010];

int n;

bool dupaX(Punct a, Punct b)
{
	if(a.X == b.X)
		return a.Y < b.Y;
	return a.X < b.X;
}

bool dupaY(Punct a, Punct b)
{
	if(a.Y == b.Y)
		return a.X < b.X;
	return a.Y < b.Y;
}

void citire()
{
	in >> n;
	for(int i = 0; i < n; i++)
	{
		in >> PointX[i].X >> PointX[i].Y;
		PointY[i].X = PointX[i].X;
		PointY[i].Y = PointX[i].Y;
	}
	sort(PointX, PointX + n, dupaX);
	sort(PointY, PointY + n, dupaY);

//	for(int i = 0; i < n; i++)
//		cout << PointX[i].X << " " << PointX[i].Y << "\n";
//		cout << endl;
//	for(int i = 0; i < n; i++)
//		cout << PointY[i].X << " " << PointY[i].Y << "\n";
//		cout << endl;
}

long long dist(Punct a, Punct b)
{
	long long difX = (a.X - b.X);
	long long difY = (a.Y - b.Y);

	return difX * difX + difY * difY;

}

long long divide(int st, int dr, Punct vec[], int len)
{
	if(dr - st == 1)
		return dist(PointX[st], PointX[dr]);

    if(dr - st == 2)
		return min(dist(PointX[st], PointX[st + 1]), min(dist(PointX[st+1], PointX[dr]), dist(PointX[st], PointX[dr])));

	int m = (st + dr) / 2;

    int counterL = 0;
    int counterR = 0;

    Punct Left[len + 10];
    Punct Right[len + 10];

    for(int i = 0; i <= len; i++)
	{
		if(vec[i].X < PointX[i].X)
		{
			Left[counterL].X = vec[i].X;
			Left[counterL].Y = vec[i].Y;
			counterL++;
		}
		else
		{
			Right[counterR].X = vec[i].X;
			Right[counterR].Y = vec[i].Y;
			counterR++;
		}
	}

    long long S1 = divide(st, m, Left, counterL - 1);
    long long S2 = divide(m + 1, dr, Right, counterR - 1);

    long long d = min(S1, S2);

    int k = 0;

    long long delta = ceil(sqrt(d));


    for(int i = 0; i <= len; i++)
    {
        if( abs( vec[i].X - PointX[m].X ) <= delta )
            {
                Distante[k].X = vec[i].X;
                Distante[k].Y = vec[i].Y;
                k++;
            }
    }

    for(int i = 0; i < k; i++)
	{
		for(int j = i + 1; j <= (i+7) && j < k; j++)
			d = min(d, dist(Distante[i], Distante[j]));
	}

	return d;

}

int main()
{
    citire();
    long long rez = divide(0, n - 1, PointY, n - 1);

    out << setprecision(6) << sqrt(rez);
    return 0;
}