#include #include typedef struct Point2D { int x, y; } Point2D; static double solve(Point2D flags[], int number_of_flags); static double distance(Point2D *pt1, Point2D *pt2); static int approx_equal(double num1, double num2, double epsilon); int main() { #ifdef TARGET_RT_MAC_CFM FILE *stream = fopen("input", "r"); #else FILE *stream = stdin; #endif int number_of_flags, index; Point2D flags[400]; for (;;) { fscanf(stream, "%d", &number_of_flags); if (number_of_flags <= 0) break; for (index = 0; index < number_of_flags; index++) fscanf(stream, "%d%d", &flags[index].x, &flags[index].y); printf("%.1f\n", solve(flags, number_of_flags)); } return 0; } static double solve(Point2D flags[], int number_of_flags) { int number_of_remaining_flags = number_of_flags; Point2D last_point = {0, 0}, direction = {0, 1}; double direction_rad = atan2(1, 0), epsilon = atan2(1, 500) / 10.0, two_pi = 3.14159265358979323846 * 2; double result = 0; while (number_of_remaining_flags > 0) { int index, best_index = 0, is_first = 1; double rad, best_rad; for (index = 0; index < number_of_flags; index++) { if (flags[index].x < 0) continue; rad = direction_rad - atan2(flags[index].y - last_point.y, flags[index].x - last_point.x); if (rad < 0) rad += two_pi; if (is_first || rad < best_rad) best_rad = rad, best_index = index; else if (approx_equal(rad, best_rad, epsilon) && distance(&last_point, &flags[index]) < distance(&last_point, &flags[best_index])) best_rad = rad, best_index = index; is_first = 0; } result += distance(&last_point, &flags[best_index]); direction.x = flags[best_index].x - last_point.x, direction.y = flags[best_index].y - last_point.y; direction_rad = atan2(direction.y, direction.x); last_point = flags[best_index]; flags[best_index].x = -1; number_of_remaining_flags--; } return result; } static double distance(Point2D *pt1, Point2D *pt2) { double dx = pt1->x - pt2->x, dy = pt1->y - pt2->y; return sqrt(dx * dx + dy * dy); } static int approx_equal(double num1, double num2, double epsilon) { return (fabs(num1 - num2) <= epsilon); }