Cod sursa(job #2466627)

Utilizator jbgvdjbfBunea Alex jbgvdjbf Data 2 octombrie 2019 19:07:21
Problema Cele mai apropiate puncte din plan Scor 5
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 7.07 kb
/*
#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;
ofstream out("intersectiesegmente.out");
ifstream in("d.in");
int main()
{
	int x, y, x1, y1, x2, y2, x3, y3, x4, y4;
	in >> x1 >> y1 >> x2 >> y2 >> x3 >> y3 >> x4 >> y4;
	if (y1 == y2)  //d1 paralela cu Ox
	{
		if (y3 == y4)  //cazul a: d2 par cu Ox
			if (y3 != y2)
			{
				cout << "paralele si nu se intersecteaza";
				out << "NU";
				system("pause");
				return 0;
			}
			else  //pe ac. axa
				if (min(x3, x4) > max(x1, x2) || max(x3, x4) < min(x1, x2))
				{
					cout << "pe ac. axa si nu se intersecteaza";
					out << "NU";
					system("pause"); return 0;
				}
				else
				{
					cout << "pe ac. axa si se intersecteaza";
					out << "DA";
					system("pause"); return 0;
				}
		if (x3 == x4)  //d2 par cu Oy
			if (y3 >= y1 && y4 <= y1 || y4 >= y1 && y3 <= y1)
			{
				cout << "Unul e paralel cu Ox, altul, cu Oy si se intersecteaza." << endl;
				out << "DA";
				system("pause"); return 0;
			}
			else
			{
				cout << "Unul e paralel cu Ox, altul, cu Oy, dar nu se intersecteaza." << endl;
				out << "NU";
				system("pause"); return 0;
			}
		//d2 oblica
		double dy = y4 - y3;
		double dx = x4 - x3;
		double m = dy / dx;
		double n = y3 - dy / dx * x3;
		cout << m << ' ' << n << endl;
		double xcalc = (y1 - n) / m;
		if (xcalc >= min(x1, x2) && xcalc <= max(x1, x2))
		{
			cout << "se intersecteaza";
			out << "DA";
			system("pause"); return 0;
		}
		else
		{
			cout << "nu se intersecteaza";
			out << "NU";
			system("pause"); return 0;
		}
	}

	if (x1 == x2)  //d1 paralele cu Oy
	{
		if (x3 == x4)  //b. d2 par cu Oy
			if (x3 != x2)
			{
				cout << "paralele si nu se int";
				out << "NU";
				system("pause"); return 0;
			}
			else
				if (min(y3, y4) > max(y1, y2) || max(y3, y4) < min(y1, y2))
				{
					cout << "pe ac. axa si nu se intersecteaza";
					out << "NU";
					system("pause"); return 0;
				}
				else
				{
					//cout << "pe ac. axa si se intersecteaza";
					out << "DA";
					system("pause"); return 0;
				}
		if (y3 == y4) //cazul a: d2 par cu Ox
			if (y1 >= y3 && y2 <= y3 || y2 >= y3 && y1 <= y3)
			{
				cout << "Unul e paralel cu Ox, altul, cu Oy si se intersecteaza." << endl;
				out << "DA";
				system("pause"); return 0;
			}
			else
			{
				cout << "Unul e paralel cu Ox, altul, cu Oy, dar nu se intersecteaza." << endl;
				out << "NU";
				system("pause"); return 0;
			}
		//d2 oblica
		double dy = y4 - y3;
		double dx = x4 - x3;
		double m = dy / dx;
		double n = y3 - dy / dx * x3;
		cout << m << ' ' << n << endl;
		double ycalc = m * x1 + n;
		cout << "ycalc=" << ycalc << endl;
		if (ycalc >= min(y3, y4) && ycalc <= max(y4, y3))
		{
			cout << "se intersecteaza";
			out << "DA";
			system("pause"); return 0;
		}
		else
		{
			cout << "nu se intersecteaza";
			out << "NU";
			system("pause"); return 0;
		}

	}
	
	if (y3 == y4) //d2 paralela cu Ox
	{
		// d1 oblica
		double dy = y2 - y1;
		double dx = x2 - x1;
		double m = dy / dx;
		double n = y1 - dy / dx * x1;
		cout << m << ' ' << n << endl;
		double xcalc = (y3 - n) / m;
		cout << "xcalc=" << xcalc << endl;
		if (xcalc >= min(x3, x4) && xcalc <= max(x3, x4))
		{
			cout << "se intersecteaza";
			out << "DA";
			system("pause"); return 0;
		}
		else
		{
			cout << "nu se intersecteaza";
			out << "NU";
			system("pause"); return 0;
		}
	}
	if (x3 == x4) //d2 paralela cu Oy
	{
		// d1 oblica
		double dy = y2 - y1;
		double dx = x2 - x1;
		double m = dy / dx;
		double n = y1 - dy / dx * x1;
		cout << m << ' ' << n << endl;
		double ycalc = m * x3 + n;
		cout << "ycalc=" << ycalc << endl;
		if (ycalc >= min(y1, y2) && ycalc <= max(y2, y1))
		{
			cout << "se intersecteaza";
			out << "DA";
			system("pause"); return 0;
		}
		else
		{
			cout << "nu se intersecteaza";
			out << "NU";
			system("pause"); return 0;
		}
	}


	cout << "oblice\n";
	// if (x2!=x1 && x4!=x3 && y2!=y1 && y4!=y3)
	{
		if ((x2 - x1)*(y4 - y3) == (y2 - y1)*(x4 - x3))
			if (y3 == (x3*(y2 - y1) - x1 * (y2 - y1) + y1 * (x2 - x1)) / (x2 - x1) && y4 == (x4*(y2 - y1) - x1 * (y2 - y1) + y1 * (x2 - x1)) / (x2 - x1))
				if ((x3 > max(x1, x2) && x4 > max(x1, x2)) || (x3 < min(x1, x2) && x4 < min(x1, x2)))
				{
					cout << "Sunt pe aceeasi dreapta, dar nu se intersecteaza." << endl;
					out << "NU";
					system("pause"); return 0;
				}
				else
				{
					cout << "Sunt pe aceeasi dreapta si se intersecteaza." << endl;
					out << "DA";
					system("pause"); return 0;
				}
			else
			{
				cout << "paralele pe drepte diferite\n";
				out << "NU";
				system("pause"); return 0;
			}
		double m1, n2, n1, m2;
		m1 = double((y2 - y1)) / (x2 - x1 );
		n1 = -m1*x1 + y1;
		m2 = double((y4 - y3)) / (x4 - x3 );
		n2 = -m2*x3 + y3;
		cout << m1 << " " << n1 << " " << m2 << " " << n2 << endl;
		//x = ((x4 - x3)*(x1*(y2 - y1) - y1 * (x2 - x1)) - (x2 - x1)*(x1*(y4 - y3) - y3 * (x4 - x3))) / ((y2 - y1)*(x4 - x3) - (y4 - y3)*(x2 - x1));
		x = (n2 - n1) / (m1 - m2);
		//y = (x*(y2 - y1) - x1 * (y2 - y1) + y1 * (x2 - x1)) / (x2 - x1);
		y = m1 * x + n1;
		cout << x << " " << y << endl;
		if (x >= min(x1, x2) && x <= max(x1, x2) && y >= min(y1, y2) && y <= max(y1, y2)
			&& x >= min(x3, x4) && x <= max(x3, x4) && y >= min(y3, y4) && y <= max(y3, y4))
		{
			cout << "Se intersecteaza." << endl;
			out << "DA";
			system("pause"); return 0;
		}
		else
		{
			cout << "Nu se intersecteaza." << endl;
			out << "NU";
			system("pause"); return 0;
		}
	}
	//cout << "Hello world!" << endl;
	system("pause"); return 0;
}
*/
#include <iostream>
#include <cmath>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream in("cmap.in");
ofstream out("cmap.out");
int n, x, y;
pair <int, int> a[100001];
double dist(pair <int, int> a, pair <int, int> b)
{
	double d = sqrt((a.first - b.first)*(a.first - b.first) + (a.second - b.second)*(a.second - b.second));
	return d;
}
double dei(int st, int dr)
{
	if (dr - st == 1)
		return dist(a[st], a[dr]);
	if (dr - st == 2)
	{
		double n1 = dist(a[st], a[dr]);
		double n2 = dist(a[st + 1], a[dr]);
		double n3 = dist(a[st], a[st + 1]);
		return min(n1, min(n2, n3));
	}
	int mij = (st + dr) / 2;
	double dst = dei(st, mij);
	double ddr = dei(mij + 1, dr);
	double d = min(dst, ddr);
	int mijst = st;
	for (int j = mij; j >= st; j--)
	{
		if (a[mij].first - a[j].first < d)
			mijst = j;
		else
			break;
	}
	int mijdr = dr;
	for (int j = mij + 1; j <= dr; j++)
	{
		if (a[j].first - a[mij].first < d)
			mijdr = j;
		else
			break;
	}
	for (int i = mijst; i <= mij; i++)
		for (int j = mij + 1; j <= mijdr; j++)
		{
			if (d > dist(a[i], a[j]))
				d = dist(a[i], a[j]);
		}
	return d;

}
int main()
{
	in >> n;
	for (int i = 0; i < n; i++)
		in >> a[i].first >> a[i].second;
	double mn = dist(a[0], a[1]);
	/*for(int i=0;i<n;i++)
	{
		for(int j=i+1;j<n;j++)
		mn=min(dist(a[i],a[j]),mn);
	}*/
	sort(a, a + n);
	mn = dei(0, n - 1);
	out.precision(10);
	out << mn;
	return 0;
}