Cod sursa(job #2072669)

Utilizator bogdanpaunFMI Paun Bogdan Gabriel bogdanpaun Data 22 noiembrie 2017 02:21:36
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.18 kb

 
#include <stdio.h>
#include <float.h>
#include <stdlib.h>
#include <math.h>
#include <algorithm>

using namespace std;

struct Point
{
    long long x, y;
};
 

int compareX(const Point &p1, const Point &p2)
{
    return p1.x < p2.x;
}

int compareY(const Point &p1, const Point &p2)
{
    return p1.y < p2.y;
}
 

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

long double bruteForce(Point P[], long long n)
{
    long double min = LDBL_MAX; // valoarea maxima pentru lonbg double
    for (long long i = 0; i < n; ++i)
        for (long long j = i+1; j < n; ++j)
            if (dist(P[i], P[j]) < min)
                min = dist(P[i], P[j]);
    return min;
}
 

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

long double verificaMediana(Point aux[], long long size, long double d)
{
    long double min = d; 
 
    sort(aux ,aux +  size , compareY); 
 
    
    for (long long i = 0; i < size; ++i)
        for (long long j = i+1; j < size && (aux[j].y - aux[i].y) < min; ++j)
            if (dist(aux[i],aux[j]) < min)
                min = dist(aux[i], aux[j]);
 
    return min;
}

long double cautaSolutie(Point *P, int n)
{
    
    if (n <= 3)
        return bruteForce(P, n);
 
    
    int mid = n/2;
    Point midPoint = P[mid];
 
    
    float solutionLeft = cautaSolutie(P, mid);
    float solutionRight = cautaSolutie(P + mid, n-mid);
 
    
    float solutie = min(solutionLeft, solutionRight);
 
   
    Point aux[n];
    int j = 0;
    for (int i = 0; i < n; i++)
        if (abs(P[i].x - midPoint.x) < solutie )
            aux[j] = P[i], j++;
 
    
    return min(solutie, verificaMediana(aux, j, solutie) );
}


long double closest(Point *P, int n)
{
    sort(P, P + n , compareX);
 
    
    return cautaSolutie(P, n);
}
 
int main()
{
    Point *P;
    int n ;
	FILE *fin=fopen("cmap.in","r");
	FILE *fout=fopen("cmap.out","w");
    fscanf(fin , "%d",&n);
	P = new Point[n]; 
	 
	for(int i=0;i<n;++i){
		long long x,y;
		fscanf(fin,"%lld %lld",&x,&y);
		P[i].x = x;
		P[i].y = y;
	}
	double d = closest(P, n);
    fprintf(fout,"%lf", d);
	free(P);
    return 0;
}