EduBrick

Как обходят многоугольник

2000 мс · 256 МБ · всё или ничего

Дан простой многоугольник — вершины перечислены в порядке обхода, самопересечений нет. Определите направление обхода и посчитайте, в скольких вершинах поворот идёт налево.

Формат ввода

В первой строке nn (3≤n≤2⋅1053 \le n \le 2 \cdot 10^5). В каждой из следующих nn строк координаты очередной вершины (∣x∣,∣y∣≤106|x|, |y| \le 10^6).

Многоугольник простой. Три подряд идущие вершины могут оказаться на одной прямой — такая вершина не считается поворотом ни налево, ни направо.

Формат вывода

Выведите в первой строке CCW, если обход против часовой стрелки, и CW иначе. Во второй строке — количество вершин, в которых поворот идёт налево.

Примеры

ввод
4
0 0
2 0
2 2
0 2
вывод
CCW
4
ввод
4
0 0
0 2
2 2
2 0
вывод
CW
0
Разбор идеи от автора задачи. Сначала попробуйте сами.
Войдите, чтобы отправлять решения.