Cod sursa(job #1018325)

Utilizator tavi.belu1994FMI Belu Andrei Octavian tavi.belu1994 Data 29 octombrie 2013 13:00:09
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.93 kb
#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;
}