ннннннннр

03.01.2023 06:53

Информатика

Есть ответ 👍

Слышали ли вы что-нибудь о лимонно-кедровом лесу (лкл)? это уникальное место с лимонными деревьями и кедровыми соснами, в котором живут удивительные звери. формально лкл можно представить как плоскость с отмеченными на ней домиками зверей. всего есть n зверей, координаты домика i-го зверя равны (xi, yi). поскольку в одном домике могут жить несколько зверей, то некоторые пары координат могут совпадать. мудрый грач живёт в лкле уже седьмой год. за это время выросло не одно поколение зверят, и с лклом произошло множество изменений. в этом году мудрый грач предложил что-то новое: превратить часть леса в заповедник. но чтобы проект заповедника был принят, он должен соответствовать требованиям министерства лесопреобразования, а именно, заповедник должен быть выпуклым многоугольником, координаты каждой из вершин заповедника должны совпадать с координатами какого-то из домиков зверей, а периметр этого многоугольника должен быть минимальным возможным. поскольку мудрый грач заботится о жителях лкла, он хочет выбрать координаты вершин заповедника так, чтобы количество зверей, чей домик оказался внутри или на границе заповедника, было как можно больше. таким образом грачу нужно узнать максимальное количество зверей, чей домик окажется внутри или на границе заповедника с минимальным периметром. же ему скорее! выпуклый многоугольник — такой многоугольник, что для любых двух его точек, отрезок, соединяющий эти точки, целиком принадлежит многоугольнику. в данной мы считаем, что выпуклый многоугольник может иметь также одну или две вершины. периметр многоугольника — сумма длин его сторон (для многоугольника только из двух вершин периметр равен удвоенной длине единственного отрезка). формат файла входных данных: в первой строке входного файла содержится одно целое число n (1 ≤ n ≤ 100 000) — количество зверей. в следующих n строках содержатся по два целых числа xi,yi (0 ≤ xi,yi ≤ 500) — координаты домика i-го жителя. формат файла выходных данных: вы должны вывести одно целое число — максимальное количество зверят, чей домик окажется внутри или на границе заповедника с минимальным периметром. пример: стандартный ввод или wise-rook.in стандартный вывод или wise-rook.out 2 500 500 500 500 2 комментарий: в примере двое зверят, находящихся в одной и той же точке. единственный многоугольник, удовлетворяющий условию, состоит из одной вершины, находящейся в той же точке (500, 500), он же обладает минимальным периметром. для такого проекта заповедника все двое зверят попадут на его границу.