Олимпиадная информатика

Задача « Вишни для Винни »

Винни-Пух любит мед. Это известно всем. Лучший подарок для Винни - это медовый торт. А что может быть лучше торта? Конечно же, медовый торт с двумя вишенками.

Поэтому Винни во время юбилея захотел отрезать себе кусочек, в котором оказались бы обе вишенки сразу. По правилам приличия в плюшевой стране принято отрезать себе кусочки четырехугольной формы путем прямолинейных разрезов через вершины торта.

И именно это правило сделало задачу невыполнимой... для Винни, но не для нас. Помогите Винни найти такие четыре вершины многоугольного выпуклого торта, чтобы обе вишенки находились в определяемом ими четырехугольнике.

Формат входного файла input.txt Первая строка содержит единственное натуральное число N -количество вершин торта (4 < N < 1000). В следующих N строках записаны координаты вершин выпуклого Л/-угольника в порядке обхода по часовой стрелке. Следующие две строки содержат координаты вишен внутри торта. Все координаты - целые числа, не превосходящие по абсолютной величине 105. Все числа в строках разделены пробелом.

Формат выходного файла output.txt В четырех строках запишите через пробел координаты четырех вершин торта. Эти вершины определяют четырехугольный кусок в порядке обхода его контура по часовой стрелке, которому принадлежат обе вишни. Вишни можно считать точками, и они принадлежат четырехугольнику, даже если они лежат на его сторонах или отстоят от них на расстоянии 10~9. Если решений несколько, выведите любое из них.

INPUT.TXT

5
0 0
0 1
1 4
2 1
2 0
1 3
1 2

OUTPUT.TXT

1 4
2 1
2 0
0 0

посмотреть решение здесь

предложено олимпиадной комиссией

function F(var Р: TPoint) : shortint;
var d : int64;
begin
d := Р..ГШ - Al) - F.x*(Y2 - Y\) + А1*У2 - А2*У1;
if d > 0 then F := 1 else F := -1;
if d = 0 then F := 0:
end:?
Приведем фрагмент программы на языке Паскаль, в котором обрабатывается основной вариант
пересечения прямой XYco сторонами многоугольника.
k := 1; i := 1;
while i, <= n do begin
j := i mod n + 1;
if (F(PЙ) = 0) Or (F(P[i])*F(P[/]) < 0) then
begin A[k] := РЩ; A[k + 1] := P[/]; Inc(fe, 2);
end;
if F(P[i]) = 0 then Inc(i);
in c(/'):
end;



close

Разбор задачи №1 "Вишни для Винни "

Проведем прямую через точки X и У, в которых находятся вишни. Пусть прямая XY пересекает стороны АВ и CD многоугольника. Отрезок этой прямой лежит внутри четырехугольника с вершинами А, В, С и D, поэтому и точки X, Утоже лежат внутри четырехугольника с вершинами А, В, С, D. Значит, ABCD - искомый четырёхугольник. Возможно, прямая попадает в вершину многоугольника, то есть некоторые две из точек А, В, С, D совпадут, но тогда просто добавим к этим точкам еще одну (любую) вершину многоугольника. Аналогично поступим, если оба конца отрезка совпадают с вершинами многоугольника (А совпадает с В и С совпадает с D). Используем функцию F, которая задает уравнение прямой XY. Её входными параметрами будут координаты вершин (Р.х; Р.у) многоугольника. Поскольку вершины А и В (а также вершины С и D) находятся по разные стороны от XY, значения функции F(A) и F(B) (а также F(C) и F(D)) будут разных знаков. Для всех остальных пар соседних вершин многоугольника значения функции Fбудут одного знака.

Олимпиадная информатика-2013

Разбор и решение задач муниципального уровня

Задача « Вишни для Винни »

Разбор задачи №1 "Вишни для Винни "

Содержание