Cod sursa(job #1016609)

Utilizator miu_mik93FMI - Paduraru Miruna miu_mik93 Data 26 octombrie 2013 15:29:52
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.19 kb
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <string>
#include <stdlib.h>
#include <assert.h>
#include <time.h>
#include <algorithm>
using namespace std;
#define NMax 100001
#define infinit 1000000000.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) );
}
int n; punct v[NMax], aux[NMax];
void interclasare(int li, int mid, int ls)
{

	int i = li, j = mid + 1, k = 0;
	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-li];
}
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)
{
	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]; 
	int midx = v[mid].x;
	double distSt = DivideEtImpera(li, mid);
	double distDr = DivideEtImpera(mid + 1, ls);
	double distt = (distSt > distDr ? distDr : distSt);
	interclasare(li, mid, ls);
	//qsort(v+li, ls, sizeof(punct), compare1);
	int nr = 0; 
	for (int i = li; i <= ls; i++)
		if (abs(midx - v[i].x) <= distt)//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(const void *a, const void *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()
{
	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));
	fclose(f); fclose(g);
	return 0;
}