Cod sursa(job #1033453)

Utilizator sziliMandici Szilard szili Data 16 noiembrie 2013 23:17:56
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 3.56 kb
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <math.h>

#define MAX_DOUBLE 999999999999999.0

using namespace std;

typedef struct point{
    long long x;
    long long y;
} POINT;


int n;
POINT xVector[100001];
POINT yVector[100001];
POINT aux[100001];

void swapElements(POINT *xVector, int index1, int index2){
    POINT sw = xVector[index1];
    xVector[index1] = xVector[index2];
    xVector[index2] = sw;
}

void quickSort(int first, int last){
    int left = first;
    int right = last;
    int pivot = xVector[(first+last)/2].x;

    do {
        while (xVector[left].x < pivot){
            left++;
        }

        while (xVector[right].x > pivot){
            right--;
        }

        if (left <= right){
            swapElements(xVector, left, right);
            left++;
            right--;
        }

    } while (left <= right);

    if (right > first){
        quickSort(first, right);
    }

    if (left < last){
        quickSort(left, last);
    }
}

double calculateDistance(POINT p1, POINT p2){
    return sqrt((double)(p1.x-p2.x)*(p1.x-p2.x) + (double)(p1.y-p2.y)*(p1.y-p2.y));
}

void mergeYVector(int first, int last, int middle){
    int left1 = first;
    int right1 = middle;
    int left2 = middle+1;
    int right2 = last;

    int index = 0;
    while (left1 <= right1 && left2 <=right2){
        if (yVector[left1].y < yVector[left2].y){
            aux[index++] = yVector[left1];
            left1++;
        } else {
            aux[index++] = yVector[left2];
            left2++;
        }
    }

     while (left1 <= right1){
        aux[index++] = yVector[left1];
        left1++;
     }

     while (left2 <=right2){
        aux[index++] = yVector[left2];
        left2++;
     }

    for (int i=0; i<index; i++){
        yVector[first + i] = aux[i];
    }
}


double findSmallestDistance(int first, int last){
    if (first == last){
        return MAX_DOUBLE;
    }
    else if (last == first+1){
        if (yVector[first].y > yVector[last].y){
            swapElements(yVector, first, last);
        }

        return calculateDistance(yVector[first], yVector[last]);
    }
    else {
        int middleIndex = (first+last)/2;

        double distanceLeft = findSmallestDistance(first, middleIndex);
        double distanceRight = findSmallestDistance(middleIndex+1, last);

        mergeYVector(first, last, middleIndex);

        double minDistance = min(distanceLeft, distanceRight);
        int auxLength = 0;

        for (int i=first; i<=last; i++){
            if (abs(yVector[i].x - xVector[middleIndex].x) <= (int)minDistance){
                aux[auxLength++] = yVector[i];
            }
        }

        for (int i=0; i<auxLength; i++){
            for (int j=i+1; j<=i+7 && j <auxLength; j++){
                if (calculateDistance(aux[i], aux[j]) < minDistance){
                    minDistance = calculateDistance(aux[i], aux[j]);
                }
            }
        }

        return minDistance;
    }

}

int main()
{
    freopen("cmap.in", "r", stdin);
    freopen("cmap.out", "w", stdout);

    scanf("%d", &n);

    int x,y;
    for (int i=0; i<n; i++){
        scanf("%d %d", &x, &y);
        xVector[i].x = x;
        xVector[i].y = y;
    }

    quickSort(0, n-1);

    for (int i=0; i<n; i++){
        yVector[i] = xVector[i];
    }

    double a = findSmallestDistance(0, n-1);

    for (int i=0; i<n; i++){

    }

    printf("%lf", a);

    return 0;
}