1246. Собака на привязи

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

Вход. В первой строке входного файла содержится n – число вершин многоугольника (известно, что 3 £ n £ 200000), затем в N строках приведены координаты вершин на плоскости, в порядке обхода их олимпийцем. Координаты - это пара действительных чисел, разделенных пробелом. Каждая координата не превышает по модулю 10²⁰⁰. Координаты во входном файле могут быть в экспоненциальной форме.

Выход. Выдать в выходной файл cw (сокращение от clockwise), если трос наматывается по часовой стрелке (если смотреть на столб сверху) и ccw (counterclockwise) в противном случае.

Пример входа

4

0 0

0 1

1 1

1 0

Пример выхода

cw

РЕШЕНИЕ

геометрия

Анализ алгоритма

Пусть (x₁, y₁), (x₂, y₂), …, (x_n, y_n) – координаты вершин выпуклого многоугольника, заданные в порядке его обхода по или против часовой стрелки. Тогда абсолютное значение выражения

S = (здесь (x_n+1, y_n+1) = (x₁, y₁))

равно площади многоугольника (формула трапеций). При этом значение S будет положительным, если координаты вершин заданы в порядке обхода по часовой стрелке и отрицательным, если против.

Реализация алгоритма

Объявим переменные, необходимые для вычислений:

double x0,y0,x1,y1,x2,y2,s;

int n,i;

Читаем входные данные. В переменных (x0, y0) храним координаты первой точки. В переменных (x1, y1) и (x2, y2) содержим координаты двух текущих соседних точек.

scanf("%d",&n);

scanf("%lf %lf",&x1,&y1);x0 = x1; y0 = y1;

В переменной s накапливаем значение приведенной выше суммы. Поскольку нас интересует только ее знак, то на каждой итерации в цикле можно не производить деление на 2.

s=0;

for(i=2;i<=n;i++)

{

scanf("%lf %lf",&x2,&y2);

s += (y2+y1)*(x2-x1);

x1 = x2; y1 = y2;

}

s += (y2+y0)*(x0-x2);

Выводим результат в зависимости от знака суммы s.

if (s>0) printf("cw"); else printf("ccw");