Pagini recente » Cod sursa (job #2576302) | Cod sursa (job #105054) | Cod sursa (job #91758) | Cod sursa (job #1687494) | Cod sursa (job #1018325)
#include <iostream>
#include <cstdio>
#include <cmath>
FILE *f,*g;
using namespace std;
double dist=100000.00000000;
void quickSort(long arr[100005][2], int left, int right){
int i = left, j = right;
float tmp;
float pivot = arr[(left + right) / 2][0];
while (i <= j)
{
while (arr[i][0] < pivot)
i++;
while (arr[j][0] > pivot)
j--;
if (i <= j)
{
tmp = arr[i][0];
arr[i][0] = arr[j][0];
arr[j][0] = tmp;
tmp = arr[i][1];
arr[i][1] = arr[j][1];
arr[j][1] = tmp;
i++;
j--;
}
}
if (left < j)
quickSort(arr, left, j);
if (i < right)
quickSort(arr, i, right);
}
void cmap(long arr[100005][2], int left, int right){
long dreapta;
dreapta=(right-left+1)/2;
double part;
if(dreapta<=3)
{
if(dreapta==2)
{
part=sqrt(pow(arr[left][0]-arr[left+1][0],2)+pow(arr[left][1]-arr[left+1][1],2));
if(part<dist)
dist=part;
}
else
{
part=sqrt(pow(arr[left][0]-arr[left+1][0],2)+pow(arr[left][1]-arr[left+1][1],2));
if(part<dist)
dist=part;
part=sqrt(pow(arr[left][0]-arr[left+2][0],2)+pow(arr[left][1]-arr[left+2][1],2));
if(part<dist)
dist=part;
part=sqrt(pow(arr[left+1][0]-arr[left+2][0],2)+pow(arr[left+1][1]-arr[left+2][1],2));
if(part<dist)
dist=part;
}
}
else
{
cmap(arr,left,dreapta);
cmap(arr,dreapta,right);
}
}
int main(){
f=fopen("cmap.in","r");
g=fopen("cmap.out","w");
long A[100005][2],n,i;
fscanf(f,"%d",&n);
for(i=1;i<=n;i++)
{
fscanf(f,"%d%d",&A[i][0],&A[i][1]);
}
quickSort(A,1,n);
cmap(A,1,n);
fprintf(g,"%f",dist);
return 0;
}