Олимпиадные задачи с решениями на Turbo Pascal
| Информационный Канал Subscribe.Ru |
| 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. |
|
Наше решение YES YES NO NO NO NO NO NO NO NO |
Edward yes yes yes no yes no no yes yes no |
Krill yes yes no yes no yes yes yes no yes |
Зайцев No No Yes Yes Yes Yes Yes No Yes No |
Vitas-i yes yes yes yes yes yes no yes yes yes |
art926 no yes no no no no no yes no no |
kuplvan yes yes no no no no no yes no no |
А вот наш вариант решения. "Наш", пожалуй, громко сказано, т.к. мои здесь только комментарии и пара строчек - скорее для красоты, чем по сути (но в результате стало на 1 переменную меньше). Сам-то я только письма пишу, задачки и решения дает сын. И не только потому, что взрослым некогда всякой ерундой заниматься, но и от того, что я многое из теории уже не помню.
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; { уравнения Ax + By + C = 0, поверим }
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.
* краниальнее - это такой медицинский термин, общее понятие для левее-правее (все-таки анатомия у нас довольно симметрична). В данном случае имеется в виду, что если очередная точка слева (идем пролив часовой стрелки), то первая еще левее, а если очередная справа, то первая еще правее.
Историческая справка Реально задача была на московской городской. Там немножко по-другому был ввод:
- в одном файле задавалось несколько ломаных линий, сначала количество ломаных, затем количество точек в ломаной;
- последняя точка тоже была задана, при этом вместо куска программы, начинающегося с комментария "это мы просто замыкаем многоугольник" шла проверка на совпадение первой и последней точек (Ну неужели вы этого не умеете?)
- было ограничено время и были тесты с большим количеством точек до 8000, так что, у кого решение с вложенным циклом, - не проскочило бы;
- в тестах не было, похоже, ситуации когда отрезок является продолжением предыдущего,
Ну а за подробностями можете обращаться: на сайт Андрея Станкевича, там скачать архив зимних сборов 2004 года - последнее сообщение на странице 2003-2004 (>1.6Mb и качает очень плохо).
Доброго всем коннекта.
KEN
Ищешь фильм? http://aslof.balzer.ru/
http://subscribe.ru/catalog/rest.cinema.filmforyou
| http://subscribe.ru/
E-mail: ask@subscribe.ru |
Отписаться
Убрать рекламу |
| В избранное | ||
