Отправляет email-рассылки с помощью сервиса Sendsay

Дистанционное обучение

Подписаться Бесплатная «Серебряная» новостная рассылка . Подписчиков 406 RSS
←   Октябрь 2008   →
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31


За последние 60 дней ни разу не выходила


Сайт рассылки: http://дистанционный-репетитор.рф
Открыта: 04-12-2005

Автор
Андрей Темнов

Статистика

406 подписчиков
0 за неделю
←   Все выпуски   →

Уроки и методика преподавания информатики для учителей www.thl.narod.ru


Задача Имеется множество (не менее трех) точек на плоскости. Определить, получим ли мы выпуклый многоугольник, если соединим эти точки в заданном порядке.
Входной файл: В первой строке число вершин, в последующих строках - координаты точек.
Выходной файл: "yes" или "no"
Например:
Ввод Вывод Ввод Вывод Ввод Вывод
4
1 1
2 1
2 2
1 2 yes 4
1 1
2 2
1 2
2 1 no 4
1 1
1 4
2 2
4 1 no

Решение.

1) 4
1 1
2 1
2 2
1 2 Обычный квадрат. Естественно, он является выпуклым многоугольником. 6) 5
4 1
0 1
3 0
2 2
1 0 Пятиконечная звезда в другую сторону.
2) 4
1 1
1 2
2 2
2 1 Тот же квадрат, но рисуется в другую сторону. Он тоже выпуклый многоугольник. 7) 6
0 0
0 2
2 1
1 1
3 2
3 0 Уголок. Просто внутренний угол. Это многоугольник, но не выпуклый.
3) 4
1 1
1 2
2 1
2 2 Восьмерка на боку или бесконечность (кому как нравится). Как справедливо заметил Vitas-i - это вообще не многоугольник. Т.к. стороны не должны иметь общих точек кроме вершин. 8) 4
1 1
2 2
3 3
3 1 Треугольник из четырех точек. Один из углов = 180. Точка 2 не является вершиной.
4) 5
1 0
2 2
3 0
0 1
4 1 Самая настоящая пятиконечная звезда. Это тоже не многоугольник. В отличие от предыдущего варианта, мы все время поворачиваем в одну сторону. 9) 4
1 1
3 3
2 2
3 1 Еще один вариант расположения точек на одной прямой. Здесь, наоборот, один из углов равен 0.
5) 4
1 1
2 1
1 2
2 2 Еще одна восьмерка, только в другую сторону. Часто одна и та же программа при обходе в одну сторону работает правильно, в другую - нет. 10) 5
1 1
2 1
2 2
2 3
1 3 Опять 180.
вариант решения.

type
point = record x,y :longint end;
direct= record a,b :longint end;
var
i,k,n:longint;
direct1, directP, directC :direct;
point1, pointP, pointC :point;
pxc:longint;
sign:longint;
b:boolean;

procedure ToDirect(BegPoint,EndPoint: point; var ItsDirect: direct);
begin
ItsDirect.a:=EndPoint.y-BegPoint.y;
ItsDirect.b:=BegPoint.x-EndPoint.x;
end;

begin
assign(input,'input.txt');
reset(input);
assign(output,'output.txt');
rewrite(output);
readln(n);
readln(point1.x,point1.y); { первая точка }
readln(pointP.x,pointP.y); { вторая точка }
ToDirect(point1, pointP, DirectP); { первый отрезок }
sign:=0; { мы еще не знаем куда крутимся }
b := true;
for i:=3 to n do
begin
readln(pointC.x,pointC.y); { так вообще неважно количество точек }
ToDirect(pointP, pointC, DirectC);
pxc:=directP.b*directC.a-directC.b*directP.a;
if sign=0 then { только на первом проходе }
begin
if pxc<>0 then sign:=trunc(pxc/abs(pxc)) { направление первого поворота }
else b:=false; { точка принадлежит стороне }
end
else
if (pxc=0) { продолжение предыдущего отрезка}
or (trunc(pxc/abs(pxc))<>sign) then { мы должны вертеться в ту же сторону }
b:=false; { не туда }
ToDirect(pointP, point1, Direct1); { первая точка должна быть }
pxc:=directC.b*direct1.a-direct1.b*directC.a; { краниальнее* очередной }
if (pxc=0) { первый - продолжение последнего }
or (trunc(pxc/abs(pxc))<>sign) then { внутренняя петля или звезда }
b:=false; { проехали начальную точку }
if not(b) then break ; { дальше и смотреть не стоит }
pointP :=pointC; { следующая вершина стала предыдущей }
directP:=directC; { и отрезок тоже }
end; { конец цикла }
if b then { только если еще не проехали }
begin { это мы просто замыкаем многоугольник }
ToDirect(pointP, point1, DirectC); { направление последнего отрезка }
pxc:=directP.b*directC.a-directC.b*directP.a;
if (pxc=0) { продолжение предыдущего отрезка}
or (trunc(pxc/abs(pxc))<>sign) then { мы должны вертеться в ту же сторону }
b:=false;
end;
if b then writeln('YES')
else writeln('NO');
close(input);
close(output);
end.
В избранное