eolymp
bolt
Try our new interface for solving problems
Məsələlər

Многоугольник

Многоугольник

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

Многоугольник состоит из n вершин и лежит на бесконечной прямоугольной сетке. Все вершины многоугольника имеют целочисленные координаты. Стороны данного многоугольника не пересекаются. Необходимо найти общую длину линейных сегментов сетки, которые лежат строго в заданном многоугольнике (см. рисунки ниже).

Giriş verilənləri

В первой строке содержится число n (3n100 000). В каждой из следующих n строк содержатся два целых числа − координаты вершин многоугольника (-5∙10^8x, y5∙10^8). Координаты задаются в порядке обхода или по, или против часовой стрелки.

Çıxış verilənləri

Вывести одно число (с точностью до 3 знаков после десятичной точки) − общую длину линейных сегментов сетки, которые лежат строго в заданном многоугольнике.

Пояснение к первому тесту

1429979622 - 1.png
  • Суммарная длина горизонтальных линий: 4/3 + 8/3 = 4

  • Суммарная длина вертикальных линий: 3 + 2 + 1 = 6

  • Поэтому общая длина равна 4 + 6 = 10

Пояснение ко второму тесту

1429979622 - 2.png
  • Суммарная длина горизонтальных линий: 1 + 2 + 4 = 7

  • Суммарная длина вертикальных линий: 9/4 + 3/2 + 7/4 = 5.5

  • Поэтому общая длина равна 7 + 5.5 = 12.5

Nümunə

Giriş verilənləri #1
3
5 1
2 4
1 1
Çıxış verilənləri #1
10.000
Mənbə ACM-ICPC Ukraine 2015, Перший етап Україна, 25 квітня 2015 року