islands.cpp

#include <cstring>
#include <cmath>
#include <iomanip>
#include <cstdio>
#define sqr(x) ((x) * (x))

#define debug(a) printf a
//#define debug(a) ;

FILE *in, *out;

int test, tests, n, s, d, i, i2, l, r, mid;

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

struct {
    int m;
    Point points[50];
} islands[50];
double floyd[50][50];

void clear_floyd(){
    int i, i2;
    for (i = 0; i < 50; i++){
        for (i2 = 0; i2 < 50; i2++){
            floyd[i][i2] = 999999999.99999;
        }
    }
}

double calc_distance_points(Point p1, Point p2){
    return std::sqrt(sqr(p1.x-p2.x) + sqr(p1.y-p2.y));
}

double calc_distance_point_line(Point p, Point p1, Point p2){
    double down = calc_distance_points(p1, p2);
    double up = (p.x * (p2.y - p1.y)) - (p.y * (p2.x - p1.x)) + (p2.x * p1.y) - (p2.y * p1.x);
    debug(("calc_distance_point_line: up is %.10f, down is %.10f\n", up, down));
    return up/down;    
}

double pythagoras(double b, double c){
    if (b > c){
        double tmp;
        tmp = b;
        b = c;
        c = tmp;
    }
    debug(("pythagoras: b is %.10f, c is %.10f\n", b, c));
    return std::sqrt(sqr(c) - sqr(b));
}

double double_equal(double a, double b){
    return std::fabs(a-b) <= 10e-9;
}

double calc_distance(int l, int r){
    // pass 1: find pair of points with shortest distance
    int i, i2, p1_ptr = 0, p2_ptr = 0;
    double distance = 999999999.999999999, tmp, tmp2;

    for (i = 0; i < islands[l].m; i++){
        for (i2 = 0; i2 < islands[r].m; i2++){
            if ((tmp = calc_distance_points(islands[l].points[i], islands[r].points[i2])) < distance){
                distance = tmp;
                p1_ptr = i;
                p2_ptr = i2;
            }
        }
    }
    
    Point p1, p2, p3, p_tmp1, p_tmp2;;

    p1 = islands[l].points[p1_ptr];
    p2 = islands[r].points[p2_ptr];
    debug(("pass 1: found pair (%d, %d) and (%d, %d)\n", p1.x, p1.y, p2.x, p2.y));

    p_tmp1 = islands[r].points[(p2_ptr + 1) % islands[r].m];
    p_tmp2 = islands[r].points[(p2_ptr - 1 + islands[r].m) % islands[r].m];
    
    tmp  = calc_distance_points(p1, p_tmp1);
    tmp2 = calc_distance_points(p1, p_tmp2);

    if (tmp < tmp2){
        p3 = p_tmp1;
    } else {
        p3 = p_tmp2;
    }
    
    debug(("pass 2: found point (%d, %d)\n", p3.x, p3.y));

    double len1, len2, len3, len4, len5, len6;
    len1 = calc_distance_point_line(p1, p2, p3);
    len2 = calc_distance_points(p1, p2);
    len3 = calc_distance_points(p1, p3);
    
    len4 = pythagoras(len1, len2);
    len5 = pythagoras(len1, len3);
    
    len6 = calc_distance_points(p2, p3);

    if (double_equal(len4 + len5, len6)){
        debug(("pythagoras success\n"));
        return len1;
    } else {
        debug(("pythagoras fail, diff is %.20f\n", std::fabs(len4 + len5 - len6)));
        return std::min(len2, len3);
    }
}

int main(){
    in = fopen("ISLANDS.INP", "r");
    out = fopen("ISLANDS.OUT", "w");

    fscanf(in, "%d", &tests);

    for (test = 0; test < tests; test++){
        fscanf(in, "%d", &n);
        fscanf(in, "%d %d", &s, &d);
        s--; d--;
        for (i = 0; i < n; i++){
            fscanf(in, "%d", &(islands[i].m));
            for (i2 = 0; i2 < islands[i].m; i2++){
                fscanf(in, "%d %d", &(islands[i].points[i2].x), &(islands[i].points[i2].y));
            }
        }
        
        clear_floyd();
        
        for (l = 0; l < n; l++){
            for (r = 0; r < n; r++){
                floyd[l][r] = std::min(floyd[l][r], std::abs(calc_distance(l, r)));
                debug(("distance from %d to %d: %.8f\n---\n", l, r, floyd[l][r]));
                floyd[r][l] = floyd[l][r];
            }
        }
        
        for (mid = 0; mid < n; mid++){
            for (l = 0; l < n; l++){
                for (r = 0; r < n; r++){
                    floyd[l][r] = std::min(floyd[l][r], floyd[l][mid] + floyd[mid][r]);
                }
            }
        }

        fprintf(out, "%.3f\n", floyd[s][d]);
    }

    fclose(in);
    fclose(out);
}