시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 256 MB | 0 | 0 | 0 | 0.000% |
В уездном городе N построили новую гоночную трассу. Трасса полностью готова к эксплуатации, необходимо лишь зарегистрировать ее во Всемирном Реестре Гоночных Трасс, но для этого необходимо выяснить ее протяженность.
Трасса представляет собой пространство, ограниченное внешним и внутренним краями трассы. Будем называть простой замкнутую ломаную, не имеющую самопересечений и самокасаний. И внешний, и внутренний края являются произвольными простыми замкнутыми ломаными, при этом ломаная внутреннего края находится строго внутри многоугольника, образованного внешним краем трассы. Траекторией движения по трассе является любая простая замкнутая ломаная, содержащаяся в многоугольнике внешнего края трассы, при этом содержащая в образованном ей многоугольнике внутренний край трассы. Траектория может иметь общие точки как с внутренним, так и с внешним краями трассы.
Протяженностью трассы, согласно правилам Всемирного Реестра Гоночных Трасс, является длина кратчайшей траектории движения по трассе.
Напишите программу, которая по описанию внутреннего и внешнего краев трассы, будет находить протяженность трассы.
Ниже приведены рисунки гоночных трасс из примеров.
Первая строка содержит единственное целое число n (3 ≤ n ≤ 258) — число звеньев ломаной внутреннего края трассы. Далее следуют n строк, содержащие пары чисел xiinner и yiinner (−1000 ≤ xiinner, yiinner ≤ 1000) — вершины ломаной внутреннего края трассы.
Следующая строка содержит единственное целое число m (3 ≤ m ≤ 258) — число звеньев ломаной внешнего края трассы. Далее следуют m строк, содержащие пары чисел xiouter и yiouter (−1000 ≤ xiouter, yiouter ≤ 1000) — вершины ломаной внешнего края трассы.
Ломаные не имеют общих точек и заданы в порядке обхода против часовой стрелки.
В единственной строке выведите одно число — протяженность трассы. Ответ должен иметь относительную или абсолютную погрешность не более 10−6.
5 -1 1 -1 -1 1 -1 0 0 1 1 4 -2 2 -2 -2 2 -2 2 2
8.0
Contest > Russian Code Cup > 2012 > RCC 2012 Final Round F번