#include #include #include #include typedef struct union_find { int32_t *parent; int32_t size; } union_find; void init_union_find (union_find * const u) { for (int32_t i = 0; i < u->size; ++i){ u->parent[i] = -1; } } union_find* new_union_find (const int32_t size) { union_find * const u = (union_find *) calloc (1, sizeof (union_find)); u->parent = (int32_t *) calloc (size, sizeof (int32_t)); u->size = size; init_union_find (u); return u; } int32_t root (union_find * const u, int32_t x) { if (u->parent[x] < 0) return x; return u->parent[x] = root (u, u->parent[x]); } int same (union_find * const u, const int32_t x, const int32_t y) { return root (u, x) == root (u, y); } void unite (union_find * const u, int32_t x, int32_t y) { x = root (u, x); y = root (u, y); if (x == y) return; if (u->parent[x] > u->parent[y]) { const int32_t swap = x; x = y; y = swap; } u->parent[x] += u->parent[y]; u->parent[y] = x; } typedef int32_t i32; typedef int64_t i64; #define ALLOC(size,type) ((type*)calloc((size),sizeof(type))) typedef struct point { i32 x, y; } point; i64 distance (point a, point b) { i64 dx = a.x - b.x; i64 dy = a.y - b.y; return dx * dx + dy * dy; } void run (void) { i32 n; scanf ("%" SCNi32, &n); point *p = ALLOC (n, point); for (i32 i = 0; i < n; ++i) { scanf ("%" SCNi32 "%" SCNi32, &p[i].x, &p[i].y); } union_find *u = new_union_find (n); i64 l = 0; i64 r = 200000000; while (r - l > 1) { i64 m = (l + r) / 2; init_union_find (u); i64 f = 100 * m * m; for (i32 i = 0; i < n; ++i) { for (i32 j = i + 1; j < n; ++j) { if (distance (p[i], p[j]) <= f) { unite (u, i, j); } } } if (same (u, 0, n - 1)) { r = m; } else { l = m; } } i64 ans = r * 10; printf ("%" PRIi64 "\n", ans); } int main (void) { run(); return 0; }