Cod sursa(job #1016493)

Utilizator miu_mik93FMI - Paduraru Miruna miu_mik93 Data 26 octombrie 2013 13:05:48
Problema Cele mai apropiate puncte din plan Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 2.18 kb
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <string>
#include <stdlib.h>
#include <assert.h>
#define MMax 100000
#include <time.h>
using namespace std;
#define NMax 100000
#define m 10
#define infinit 10000000.0
struct punct
{
	int x, y;
};
inline double dist( punct a, punct b )
{
    return sqrt( pow(( a.x - b.x ), 2) + pow(( a.y - b.y ), 2) );
}

void interclasare(int li, int mid, int ls, punct *v)
{

	int i = li, j = mid + 1, k = 0; punct aux[NMax];
	while (i <= mid && j <= ls)
	{
		if (v[i].y < v[j].y)
		{
			aux[k++] = v[i++];
		}
		else
		{
			aux[k++] = v[j++];
		}
	}
	while (i <= mid)
	{
		aux[k++] = v[i++];
	}
	while (j <= ls)
	{
		aux[k++] = v[j++];
	}
	for (int i = li; i<=ls; i++)
		v[i] = aux[i];
}
int compare1(void const *a, void const *b)
{
	punct * _a = (punct*)a; punct * _b = (punct*)b;
	return (_a->y - _b->y);
}
double DivideEtImpera(int li, int ls, int n, punct v[])
{
	if (ls - li == 0)
	{
		return infinit;
	}
	if (ls - li == 1)
	{
		return dist(v[ls], v[li]);
	}
	int mid = (li + ls)/2;
	punct midp = v[mid];
	double distSt = DivideEtImpera(li, mid, n, v);
	double distDr = DivideEtImpera(mid + 1, ls, n, v);
	double distt = (distSt > distDr ? distDr : distSt);
	//interclasare(li, mid, ls, v);
	qsort(v, ls, sizeof(punct), compare1);
	int nr = 0; punct aux[NMax];
	for (int i = li; i <= ls; i++)
		if (dist(v[i], midp) <= distt)
			aux[nr++] = v[i];
	double distmin = distt;
	for (int i = 0; i < nr; i++)
		for (int j = i+1; j < nr && j < i+8; j++)
		{
			double formula = dist(aux[i], aux[j]);
			distmin = (distmin > formula ? formula : distmin);
		}
	return distmin;
}
int compare(void const *a, void const *b)
{
	punct * _a = (punct*)a; punct * _b = (punct*)b;
	if (_a->x == _b->x)
		return (_a->y - _b->y);
	else
		return (_a->x - _b->x);
}
int main()
{
	int n; punct v[NMax];
	FILE *f = fopen("cmap.in", "r");
	FILE *g = fopen("cmap.out", "w");
	fscanf(f, "%d", &n);
	for (int i=0; i<n; i++)
	{
		fscanf(f, "%d %d", &v[i].x, &v[i].y);
	}
	qsort(v, n, sizeof(punct), compare);
	fprintf(g, "%.6lf\n", DivideEtImpera(0, n-1, n, v));
	fclose(f); fclose(g);
	return 0;
}