UVa 10245

The Closest Pair Problem.cpp

#include <stdio.h>
#include <math.h>
#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;

struct Point{
	double x;
	double y;
};

bool cmp(Point &obj1, Point &obj2)
{
	return obj1.x < obj2.x;
}

double GetDistance(Point &a, Point &b)
{
	return (a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y);
}

int main()
{
	//freopen("output.txt", "w", stdout);
	int N;
	vector<Point> pointList(10001);
	while (~scanf("%d", &N))
	{
		for (int i = 0; i < N; i++)
		{
			scanf("%lf%lf", &pointList[i].x, &pointList[i].y);
		}

		double resultDistance = 100000000;
		if (N == 0)
		{
			break;
		}
		sort(pointList.begin(), pointList.begin() + N, cmp);
		for (int i = 0; i < N; i++)
		{
			for (int j = i + 1; j < N; j++)
			{
				//if (pointList[i].x + resultDistance <= pointList[j].x)  //WA
				//if ((pointList[i].x - pointList[j].x)*(pointList[i].x - pointList[j].x) >= resultDistance)  //AC
				if (pointList[i].x + sqrt(resultDistance) <= pointList[j].x) //AC
				{
					break;
				}

				double currentDistance = GetDistance(pointList[i], pointList[j]);
				if (currentDistance < resultDistance)
				{
					resultDistance = currentDistance;
				}
			}
		}

		resultDistance = sqrt(resultDistance);
		if (resultDistance >= 10000)
		{
			printf("INFINITY\n");
		}
		else
		{
			printf("%.4lf\n", resultDistance);
		}
	}
	return 0;
}