→ Обратите внимание
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3676 |
| 2 | Kevin114514 | 3659 |
| 3 | jiangly | 3640 |
| 4 | turmax | 3450 |
| 5 | tourist | 3408 |
| 6 | strapple | 3360 |
| 7 | Um_nik | 3354 |
| 8 | squareOf105 | 3348 |
| 9 | maroonrk | 3312 |
| 10 | idontwannadothis…e | 3191 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 155 |
| 2 | nik_exists | 151 |
| 3 | maspy | 149 |
| 4 | AmShZ | 145 |
| 5 | Um_nik | 143 |
| 6 | Errichto | 139 |
| 7 | BledDest | 136 |
| 8 | adamant | 135 |
| 9 | maroonrk | 132 |
| 10 | cry | 130 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2026 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 08.11.2026 18:16:28 (g2).
Десктопная версия, переключиться на мобильную.
При поддержке
Находишь самую дальнюю точку(она в вершине) Находишь самую ближнюю точку(либо в вершине, либо пересечение высоты со стороной) Из площади с большим радиусом вычитаешь меньший Высоту нужно пытаться применить только с остроугольными треугольниками, проверить можно по теореме пифагора
Можно по подробнее
Нам требуется найти радиусы двух окружностей, которые образует многоугольник при движении. Радиус большей равен максимальному расстоянию от центра до вершины многоугольника. Радиус меньшей равен min( расстоянию до ближайшей точки, расстоянию до отрезка образуемого двумя последовательными точками ). Ответ: площадь первого круга — площадь второго
а как найти " min( расстоянию до ближайшей точки, расстоянию до отрезка образуемого двумя последовательными точками)"
Кратчайшее расстояние от точки до отрезка — это либо расстояние от точки до одного из концов отрезка, либо длина перпендикуляра к отрезку.
Пусть O — точка, AB — отрезок. Посмотрим на углы OAB и OBA. Если хотя бы один из них тупой, то надо просто выбрать минимум из длин OA и OB. Чтобы проверить, что угол OAB тупой, надо найти скалярное произведение векторов OA и AB, если оно больше нуля, то угол тупой (почему больше нуля, а не меньше? скалярное произведение правильно показывает знак, только если векторы отложить из одной точки). И все аналогично для угла OBA.
Если же оба угла острые, минимум достигается на перпендикуляре к отрезку. Строим линию ax+by+c=0, проходящую через точки A и B. Это делается так: a = By — Ay, b = Ax — Bx, c = -a*Ax — b*Ay. После этого расстояние от точки O до прямой вычисляется по формуле abs(a*Ox + b*Oy + c) / sqrt(a*a + b*b).
А почему a = By — Ay.
Можно и наоборот: a = Ay — By, b = Bx — Ax. Главное, чтоб в одном случае координата одной точки была с минусом, а в другом случае — другой точки.
Эти формулы выводятся из уравнения линии, проходящей через две точки: (x — Ax) / (Bx — Ax) = (y — Ay) / (By — Ay). Но их проще запомнить, чем выводить каждый раз заново. А если переставить точки местами, как раз поменяются знаки у коэффициентов a и b.