A Marketing Strategy (Closest-pair problem)

입력 파일이 좌표(x,y)로 주어지고 가장 가까운 두 점을 찾는 문제.

Divide-conquer 기법을 사용한 Closest-pair problem(최근접 점의 쌍)으로 문제를 해결한다.

Problem

A telephone company seeks to claim they provide high-speed broadband access to customers. It will suffice for marketing purposes if they can create just one such link directly connecting two locations.  As the cost for installing such a pair of locations are the shortest distance apart so as to provide the cheapest possible implementation of this marketing strategy. More precisely, given a set of points in the plane, find the distance between the closest pair of points provided this distance is less than some limit. If the closest pair is too far apart, marketing will have to opt for some less expensive strategy.

 

Input

The input set starts with an integer N(0 ≤ N≤ 30), which denotes the number of points in this set.  The next N lines contain the coordinates of N two-dimensional points. The two numbers denote the x- and y- coordinates of N two-dimensional points. The two numbers denote the x- and y-coordinates, respectively.  The input is terminated by a set whose N =0, which should not be processed.  All coordinates will have values less than 40,000 and be non-negative. Algorithms - 3

 

Output

For each input set, produce a single line of output containing a floating point number (with two digit after the decimal point) which denotes the distance between the closest two points.  If there do not exit two points whose distance is less than 10,000, print the line “Infinity”

 

Sample Input/Output

//Input_1.txt
5
0 2
6 67
39 107
43 71
189 140
0

//Output_1.txt
36.22

 

Solution

#define _CRT_SECURE_NO_WARNINGS
#define NUMBER_OF_FILES 5
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

typedef struct {
    int x;
    int y;
} coord;

double min = -1;

double Distance(coord* a, coord* b) {
    double dist;
    dist = sqrt(pow(a->x - b->x, 2) + pow(a->y - b->y, 2));
    if (min == -1 || dist < min) {
        min = dist;
    }
    return dist;
}

double Algorithm(coord* point, int left, int right, int size) {
    double d[4];
    if (size == 2) {
        return Distance(point + left, point + right);
    }
    else if (size == 3) {
        for (int i = 0; i < 4; i++) {
            if (i == 2)
                d[i] = Distance(point + i, point);
            else if (i == 3)
                d[i] = min;
            else
                d[i] = Distance(point + i, point + i + 1);
            if (d[i] < min)
                min = d[i];
        }
        return min;
    }
    else {
        coord* temp = (coord*)malloc(sizeof(coord) * size);

        double dist, cpr, cpl;
        double min_d = -1;
        int mid = (left + right) / 2;
        int n = 0;

        cpl = Algorithm(point, left, mid, mid - left + 1);
        cpr = Algorithm(point, mid + 1, right, right - mid);
        dist = cpl < cpr ? cpl : cpr;

        for (int i = left; i <= right; i++) {
            if (abs((point + i)->x - (point + mid)->x) < dist) {
                *(temp + n) = *(point + i);
                n++;
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                min_d = dist < Distance(temp + i, temp + j) ? dist : Distance(temp + i, temp + j);
                if (min_d < dist) {
                    dist = min_d;
                }
            }
        }
        free(temp);
        return dist;
    }
}

int Compare(const void* p1, const void* p2) {
    const coord* p, * q;
    p = (const coord*)p1;
    q = (const coord*)p2;

    if (p->x > q->x)
        return 1;
    else if (p->x == q->x)
        return 0;
    else
        return -1;
}

int main(void) {
    char Input[5][15] = {
       "Input_1.txt", "Input_2.txt", "Input_3.txt", "Input_4.txt", "Input_5.txt"
    };
    char Output[5][15] = {
        "Output_1.txt", "Output_2.txt", "Output_3.txt", "Output_4.txt", "Output_5.txt"
    };
    double result;

    for (int f = 0; f < NUMBER_OF_FILES; f++) {
        FILE* input;
        input = fopen(Input[f], "r");
        FILE* output;
        output = fopen(Output[f], "w");

        int size;
        int a = fscanf(input, "%d", &size);
        coord* point = (coord*)malloc(sizeof(coord) * size);
        for (int i = 0; i < size; i++) {
            a = fscanf(input, "%d %d", &(point + i)->x, &(point + i)->y);
        }

        qsort(point, (size_t)size, sizeof(coord), Compare);

        if (output != NULL) {
            result = Algorithm(point, 0, size - 1, size);
            if (result < 10000)
                fprintf(output, "%.2lf", result);
            else
                fprintf(output, "Infinity");
            min = 10000;
            free(point);
        }
        else {
            printf("Error.");
            exit(1);
        }
        fclose(output);
    }
    return 0;
}