Cod sursa(job #2491761)

Utilizator alex.jilavu17alex jilavu alex.jilavu17 Data 13 noiembrie 2019 08:47:58
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.12 kb
#include <iostream>
#include <float.h> 
#include <stdlib.h> 
#include <math.h>
#include <fstream>

using namespace std;

struct Point
{ 
	int x, y; 
}; 

int compareX(const void* a, const void* b) 
{ 
	Point *p1 = (Point *)a, *p2 = (Point *)b; 
	return (p1->x - p2->x); 
} 

int compareY(const void* a, const void* b)
{ 
	Point *p1 = (Point *)a, *p2 = (Point *)b; 
	return (p1->y - p2->y); 
} 

float dist(Point p1, Point p2)
{ 
	return sqrt( (p1.x - p2.x)*(p1.x - p2.x) + 
				(p1.y - p2.y)*(p1.y - p2.y) 
			); 
} 

float bruteForce(Point P[], int n)
{ 
	float min = FLT_MAX; 
	for (int i = 0; i < n; ++i) 
		for (int j = i+1; j < n; ++j) 
			if (dist(P[i], P[j]) < min) 
				min = dist(P[i], P[j]); 
	return min; 
} 

float min(float x, float y) 
{ 
	return (x < y)? x : y; 
} 

float stripClosest(Point strip[], int size, float d)
{ 
	float min = d;

	for (int i = 0; i < size; ++i) 
		for (int j = i+1; j < size && (strip[j].y - strip[i].y) < min; ++j) 
			if (dist(strip[i],strip[j]) < min) 
				min = dist(strip[i], strip[j]); 

	return min; 
} 

float closestUtil(Point Px[], Point Py[], int n) 
{
	if (n <= 3) 
		return bruteForce(Px, n); 

	int mid = n/2; 
	Point midPoint = Px[mid]; 

	Point Pyl[mid+1];
	Point Pyr[n-mid-1];
	int li = 0, ri = 0;
	for (int i = 0; i < n; i++) 
	{ 
        if (Py[i].x <= midPoint.x)
            Pyl[li++] = Py[i];
        else
            Pyr[ri++] = Py[i];
	} 

	float dl = closestUtil(Px, Pyl, mid);
	float dr = closestUtil(Px + mid, Pyr, n-mid); 

	float d = min(dl, dr);

	Point strip[n];
	int j = 0; 
	for (int i = 0; i < n; i++) 
		if (abs(Py[i].x - midPoint.x) < d) 
			strip[j] = Py[i], j++; 

	return min(d, stripClosest(strip, j, d) );
} 

float closest(Point P[], int n)
{ 
	Point Px[n]; 
	Point Py[n]; 
	for (int i = 0; i < n; i++) 
	{ 
		Px[i] = P[i]; 
		Py[i] = P[i]; 
	} 

	qsort(Px, n, sizeof(Point), compareX); 
	qsort(Py, n, sizeof(Point), compareY); 

	return closestUtil(Px, Py, n); 
} 

int main() 
{ 
	ifstream fin("cmap.in");
	ofstream fout("cmap.out");
    Point P[100000];
    int n;
    fin >> n;
    for (int k = 0; k < n; k++)
        fin >> P[k].x >> P[k].y;
	fout << closest(P, n);
	return 0; 
}