Earrings
Пролетен Турнир по Информатика, 2014
Time Limit: 0.7s, Memory Limit: 64MiB
Ели и Крис бяха почти готови за петъчното си излизане, единствено оставаше да си изберат обеци. Крис отиде до съседната стая за да вземе нейната и кутията на Ели, но на връщане се спъна и разпиля съдържанието им по пода. Сега двете момичета не са сигурни кои от обеците принадлежат на коя от тях.

Тъй като бързаха да излязат, Ели предложи да разпределят обеците в две множества, които са оптимални в известен смисъл, и всяко момиче вземе обеците от едно от тях. За простота те считат обеците като точки в равнината, а "оптималността" на множествата е разстоянието между двете най-отдалечени обеци от едно и също множество. Така колкото по-малко е това разстояние, толкова по-вероятно е двете обеци да са паднали от една и съща кутия. Сега момичетата се чудят коя обеца в кое множество да принадлежи, за да може това разстояние да е минимално.

Разглеждайки задачата по-абстрактно, тя се свеждо до това да разпределите N равнинни точки (Xi, Yi) в две множества, така че разстоянието между най-далечните точки във всяко множество е минимално. По-конкретно те искат по-голямото от двете най-големи растояния да е минимално. Например ако имат едно разпределение, в което първото множество има максимално разстояние 2, а второто 6, и друго, в което първото множество има максимално разстояние 4, а второто 5, то момичетата биха избрали второто, тъй като max(4, 5) < max(2, 6).

Напишете програма, която намира максималното разстояние при оптимално разпределение на точките в две множества.
Вход
На първия ред на стандартния вход ще бъде зададено цялото число N – броя обеци (точки), които са се разпилели. Следват N на брой реда, всеки задаващ двойка цели числа Xi и Yi, задаващи координатите на всяка от обеците.
Изход
На единствен ред на стандартния изход изведете едно число с плаваща запетая – отговора на задачата. Отговорът ще бъде зачетен за верен при абсолютна или релативна разлика, по-малка от 10-9.
Ограничения
  • 2 ≤ N ≤ 2,000
  • 0 ≤ Xi, Yi ≤ 10,000
Примерен Вход Примерен Изход
9 0 0 6 8 6 5 4 4 1 2 0 2 2 1 4 6 5 4 4.472135955
Възможно оптимално разпределение е в първото множество да са точките {(0, 0), (0, 2), (1, 2), (2, 1)}, а в другото {(4, 4), (4, 6), (5, 4), (6, 5), (6, 8)}. Така максималното разстояние в първото множество е 2.236067978, а във второто е 4.472135955, правейки отговора по-голямото от двете.
Мрън!