Форум: "Основная";
Текущий архив: 2003.01.13;
Скачать: [xml.tar.bz2];
Вниз
Олимпиадная задача 1 Найти похожие ветки
← →
pumba (2003-01-02 08:14) [0]Помогите решить задачку. Я все бьюсь над ней, но не могу решить. Или линк укажите на похожую задачу(только не на абстрактный сайт)
Миротворцы ООН в одной из горячих точек планеты обезвреживали минное поле следующим образом. Имея карту, на которой каждая мина задана своими целочисленными декартовыми координатами, они, обратив внимание на то, что никакие 3 мины не лежат на одной прямой, протянули специальный шнур от мины к мине так, чтобы он образовал выпуклый многоугольник минимального периметра, при этом все остальные мины оказались внутри многоугольника. Обезвредив соединенные мины, они вновь протянули шнур по тому же принципу и опять обезвредили соединенные шнуром мины. Так продолжалось до тех пор, пока очередной шнур оказалось невозможно протянуть, руководствуясь изложенными правилами. Сколько мин осталось обезвредить и сколько раз саперам приходилось протягивать шнур?
Ввод-вывод
Вы вводите с клавиатуры количество мин N (3 <= N <= 1000), далее - N раз считываете с клавиатуры по 2 целых числа X и Y через пробел - координаты очередной мины (-32000 <= X <= 32000), (-32000 <= Y <= 32000).
Вы выводите на экран два числа через пробел - количество оставшихся мин и количество операций по натягиванию шнура.
Пример
Ввод> 9
Ввод>0 0 0 8 6 8 6 0 1 1 1 7 5 7 5 1 3 2
Вывод< 1 2
← →
Igorek (2003-01-02 10:56) [1]
> Так продолжалось до тех пор, пока очередной шнур оказалось
> невозможно протянуть, руководствуясь изложенными правилами.
>
Непонятно - вокруг множества точек всегда можно натянуть выпуклую оболочку. Если мины две, то получиться отрезок, если одна - точка. Три и более на одной прямой не может быть по условию. Разве только точек 0.
Решение: надо сэмулировать процесс натягивания выпуклой оболочки. Потом повторять процедуру, пока не достигнем конечного состояния.
Натягивание выпуклой оболочки:
1) находим крайнюю нижнюю точку (она становиться первой и текущей); текущий угол ставим 0;
2) среди остальных выбираем точку, которая образует с текущей вектор с минимальным углом к оси ординат, но больше текущего угла; она становится текущей; угол становиться текущим углом;
3) повторяем процедуру 2 до тех пор, пока текущая точка не станет первой;
← →
pumba (2003-01-02 13:21) [2]?????
← →
Sha (2003-01-02 14:26) [3]Если хочешь, чтобы помогли, то скажи, что именно у тебя вызывает трудности, как пробовал решать? Иначе получается, что ты просто хочешь, чтобы кто-то решил за тебя эту задачу. Не думаю, что она кого-нибудь заинтересует и ее решат полностью ввиду своей примитивности - это скорее домашнее задание, а не олимпиадная задача.
← →
Yegor Derevenets (2003-01-02 14:39) [4]> Sha
Не думаю, что алгоритм построения выпуклой оболочки - так уж просто. Я его писал дома с книжкой часа два. Или три. При чём мне его еще объясняли перед этим... Ладно, я тупой. Это я и так знаю.
Теперь о задаче.
В Кормене есть подробное объяснение алгоритма Джарвиса и Грэхема. Это со страницы 822. Выбираем, какой подходит лучше для конкретной задачи. Посмотри по асимптотике (кажется, Джарвис лучше подходит). Хотя это и не важно. На современных компах с такими ограничениями всё одинаково будет работать. :-)
Ещё надо понять, почему сказано многоугольник минимального периметра. Возможно, задача с подвохом.
Если интересует, пиши на мыло. Пришлю так и быть Graham-scan (когда-то он у меня работал). :-) А задачу мне решать влом! А 9-10 числа олимпиада!
Уважаемый модератор, не выкидывайте весь мой спам. :-)
Удачи!
← →
Sha (2003-01-02 15:09) [5]2Yegor Derevenets (02.01.03 14:39)
Писал от силы 10 мин.
Естественно, неоптимально. Естественно, использовал, что нет 3-х точек на прямой. Но это - пусть автор поупражняется.
procedure TForm1.Button16Click(Sender: TObject);
const
Count= 9;
p: array [0..Count-1] of TPoint=(
(X:0; Y:0), (X:0; Y:8), (X:6; Y:8),
(X:6; Y:0), (X:1; Y:1), (X:1; Y:7),
(X:5; Y:7), (X:5; Y:1), (X:3; Y:2));
var
Used: array[0..Count-1] of boolean;
Rest, Loop, i, i1, i2, lu, rd: integer;
begin;
FillChar(Used,Count,false);
Rest:=Count; Loop:=0;
while Rest>2 do begin;
inc(Loop);
// Find left/up and right/down corners
lu:=-1; rd:=-1;
for i:=0 to Count-1 do if (not Used[i]) then begin;
if ((lu<0) or (p[lu].X>p[i].X) and (p[lu].Y>=p[i].Y)) then lu:=i;
if ((rd<0) or (p[rd].X<p[i].X) and (p[rd].Y<=p[i].Y)) then rd:=i;
end;
// Move from left/up corner to right
i2:=lu;
repeat;
dec(Rest); Used[i2]:=true; i1:=i2; i2:=-1;
for i:=0 to Count-1 do
if (not Used[i]) and (p[i].X>p[i1].X) and ((i2<0)
or ((p[i].Y-p[i1].Y)*(p[i2].X-p[i1].X)<(p[i2].Y-p[i1].Y)*(p[i].X-p[i1].X)))
then i2:=i;
until i2<0;
if i1=rd then inc(Rest);
// Move from right/down corner to left
i2:=rd;
repeat;
dec(Rest); Used[i2]:=true; i1:=i2; i2:=-1;
for i:=0 to Count-1 do
if (not Used[i]) and (p[i].X<p[i1].X) and ((i2<0)
or ((p[i].Y-p[i1].Y)*(p[i2].X-p[i1].X)<(p[i2].Y-p[i1].Y)*(p[i].X-p[i1].X)))
then i2:=i;
until i2<0;
if i1=lu then inc(Rest);
end;
ShowMessage(IntToStr(Rest)+" "+IntToStr(Loop));
end;
← →
Yegor Derevenets (2003-01-02 15:21) [6]> Sha
Если работает, причем если точки не заданы в порядке обхода по какой-нибудь стрелке, я рад за Вас. Сам знаю, что не самый лучший в программировании... Кстати, похоже на правду. Кроме вот этого:
while Rest>2 do begin ;
Ладно, не будем превращать конференцию в личную беседу - кто умнее. :-)
Всё. Пошел кушать. :-)
Graham-scan (общий случай):
const
FileIn="Graham.in";
FileOut="Graham.out";
MaxN=1000;
Eps=1E-7;
type
TNode=record
X, Y: Extended;
SortValue: Extended;
end;
var
N: LongInt;
Nodes: array [1..MaxN] of TNode;
NFirstNode: LongInt;
Stack: array [1..MaxN] of LongInt;
StackLen: LongInt;
procedure ReadData;
var
FIn: Text;
NNode: LongInt;
begin
Assign (FIn, FileIn);
Reset (FIn);
Readln (FIn, N);
for NNode:=1 to N
do Readln (FIn, Nodes [NNode].X, Nodes [NNode].Y);
Close (FIn);
end;
procedure QuickSort (Lo, Hi: LongInt);
procedure Sort (l, r: LongInt);
var
i, j: LongInt;
Node: TNode;
begin
i:=l;
j:=r;
repeat
while Nodes [i].SortValue<Nodes [(l+r) div 2].SortValue
do Inc (i);
while Nodes [(l+r) div 2].SortValue<Nodes [j].SortValue
do Dec (j);
if i<=j
then begin
Node:=Nodes [i];
Nodes [i]:=Nodes [j];
Nodes [j]:=Node;
Inc (i);
Dec (j);
end;
until i>j;
if l<j
then Sort(l,j);
if i<r
then Sort(i,r);
end;
begin
Sort (Lo, Hi);
end;
procedure Solve;
function Top: LongInt;
begin
Top:=StackLen;
end;
function NextToTop: LongInt;
begin
NextToTop:=Top-1;
end;
procedure Push (aNNode: LongInt);
begin
Inc (StackLen);
Stack [StackLen]:=aNNode;
end;
procedure Pop;
begin
Dec (StackLen);
end;
var
NNode: LongInt;
function RightDirect: Boolean;
var
X0, Y0, X1, Y1, X2, Y2: Extended;
begin
X0:=Nodes [Stack [NextToTop]].X;
Y0:=Nodes [Stack [NextToTop]].Y;
X1:=Nodes [Stack [Top]].X;
Y1:=Nodes [Stack [Top]].Y;
X2:=Nodes [NNode].X;
Y2:=Nodes [NNode].Y;
RightDirect:=(X1-X0)*(Y2-Y0)-(X2-X0)*(Y1-Y0)<Eps;
end;
begin
NFirstNode:=1;
for NNode:=2 to N
do if (Nodes [NNode].Y<Nodes [NFirstNode].Y) or
((Nodes [NNode].Y=Nodes [NFirstNode].Y) and
(Nodes [NNode].X<Nodes [NFirstNode].X))
then NFirstNode:=NNode;
for NNode:=1 to N
do begin
Nodes [NNode].X:=Nodes [NNode].X-Nodes [NFirstNode].X;
Nodes [NNode].Y:=Nodes [NNode].Y-Nodes [NFirstNode].Y;
end;
for NNode:=1 to N
do if NNode=NFirstNode
then Nodes [NNode].SortValue:=1
else Nodes [NNode].SortValue:=Nodes [NNode].Y/Sqrt (Sqr (Nodes [NNode].X)+Sqr (Nodes [NNode].Y));
Inc (N);
QuickSort (1, N);
NFirstNode:=1;
for NNode:=2 to N
do if (Nodes [NNode].Y<Nodes [NFirstNode].Y) or
((Nodes [NNode].Y=Nodes [NFirstNode].Y) and
(Nodes [NNode].X<Nodes [NFirstNode].X))
then NFirstNode:=NNode;
StackLen:=0;
Push (NFirstNode);
NNode:=1;
if NNode=NFirstNode
then Inc (NNode);
Push (NNode);
Inc (NNode);
if NNode=NFirstNode
then Inc (NNode);
Push (NNode);
for NNode:=3 to N
do begin
while RightDirect
do Pop;
Push (NNode);
end;
end;
procedure WriteData;
var
FOut: Text;
NNode: LongInt;
begin
Assign (FOut, FileOut);
Rewrite (FOut);
for NNode:=1 to StackLen
do Writeln (FOut, Nodes [Stack [NNode]].X+Nodes [NFirstNode].X:0:4, #32,
Nodes [Stack [NNode]].Y+Nodes [NFirstNode].Y:0:4);
Close (FOut);
end;
procedure Main;
begin
ReadData;
Solve;
WriteData;
end;
begin
Main;
end.
← →
Yegor Derevenets (2003-01-02 15:22) [7]> Sha
Если работает, причем если точки не заданы в порядке обхода по какой-нибудь стрелке, я рад за Вас. Сам знаю, что не самый лучший в программировании... Кстати, похоже на правду. Кроме вот этого:
while Rest>2 do begin ;
Ладно, не будем превращать конференцию в личную беседу - кто умнее. :-)
Всё. Пошел кушать. :-)
Graham-scan скоро вышлю.
← →
Sha (2003-01-02 16:08) [8]2 Yegor Derevenets (02.01.03 15:22)
> Если работает, причем если точки не заданы в порядке обхода по какой-нибудь стрелке, я рад за Вас.
Ну, это легко проверяется. Я рад, что вы рады :)
> Кстати, похоже на правду. Кроме вот этого: while Rest>2 do begin;
Что эдесь вас огорчило? Я по-прежнему рад :)
Страницы: 1 вся ветка
Форум: "Основная";
Текущий архив: 2003.01.13;
Скачать: [xml.tar.bz2];
Память: 0.48 MB
Время: 0.01 c
