INFOMAN брой 17
/*
ЗМС'2000
Задача C: Купчини сняг
Задача: Да се намери сумата от разстоянията от всеки връх на граф до изпъкна-
лата му обвивка.
Пълно условие: И тази зима много изненада кмета на града г-н Градьо Градски.
От една страна падна страшно много сняг. А от друга страна, фирмите "Джаста
ООД" и "Праста ООД" които г-н Градски беше наел да почистват снега, както се
полага на дружества с ограничена отговорност,извършиха ограничено почистване.
Вместо да извозят снега извън града, те го струпаха по кръстовищата и обяви-
ха, че парите, които им е дала общината не стигат за повече. Сега г-н Град-
ски се видя в чудо, седи и си блъска главата - как да извози купчините сняг,
натрупани на всяко от N-те кръстовищата на града (N не е по-голямо от 500)
до околовръстния път, където спокойно могат да изчакат до пролетта. Снегът
от кръстовищата намиращи се на околовръстния път (представляващ затворен,
изпъкнал полигон), разбира се не е нужно да се извозва. Градоначалникът раз-
полага със списък на кръстовищата, номерирани от 1 до N, като в списъка са
зададени координатите на кръстовищата - цели положителни числа в интервала
[-10000,10000], подредени в нарастващ ред на номерата на кръстовищата. Градо-
началникът има и списък на всичките M улици на града, представени като двой-
ки от номера на кръстовища (M не е повече от 1500). За съжаление улиците на
града са доста криви, затова се наложило да бъдат измерени и да се добавят в
списъка и точните им дължини - цели числа, не по големи от 20. Известно е,
че на всяко кръстовище снегът, който е натрупан се побира в един самосвал.
Затова задачата е да се определи за всяко от кръстовищата най-близкото
кръстовище, намиращо се на околовръстния път, където да бъде изхвърлен сне-
гът. Помогнете на градоначалника - напишете програма SNOW.EXE, която да на-
мери оптималното решение на задачата, та със спестените пари да може да се
почисти следващият сняг, който рано или късно пак ще ни изненада.
Входните данни са зададени в текстов файл SNOW.INP, в първия ред на
който са само числата N и M, разделени с един интервал. Всеки от следващите
N реда съдържа двете координати на едно кръстовище, подредени по нарастващ
ред на номерата на кръстовищата, разделени с един интервал. Всеки от послед-
ните M реда на входния файл съдържа номерата на две кръстовища, които са кра-
ища на една улица и нейната дължина, разделени с по един интервал.
Като резултат от работата на програмата изведете в текстов файл SNOW.OUT
сумата от намерените за всяко кръстовище минимални разстояния до околовръст-
ния път.
Пример
SNOW.INP SNOW.OUT
6 9 13
0 6
0 2
-2 -1
-4 -3
3 -2
5 -3
1 2 10
1 4 11
1 6 13
2 3 6
2 5 9
3 4 4
3 5 2
4 6 12
5 6 1
Решение: Не е трудно да се забележи, че задачата може да се сведе до 2 стан-
дартни задачи: намиране на изпъкнала обвивка на множество от точки в равнина-
та и намиране на най-кратък път от от една точка - околовръстното (как става
това ще опишем по-долу) до всички останали (последното е еквивалентно на об-
ратния път) за ненасочен граф.
За намиране на изпъкналата обвивка на кръстовищата, ще използваме алго-
ритъм, използващ формулата за ориентирано лице на триъгълник. Алгоритъмът е
следния:
X = точката с най-голяма x координата
Отбележи X като принадлежаща на обвивката
Повтаряй безкрайно:
Вземи произволна Y <> X
За I := A[0] до А[n] и I <> X и I <> Y прави:
Aко d( X, Y, I ) < 0, то Y := I
Ако Y принадлежи на обвивката, то край
Отбележи Y като принадлежаща на обвивката
X := Y
Където A[i] са точките от входното множество, а X, Y, I са просто точки (кои-
то всъщност са променливи.)
С това първата част от задачата е решена. За втората част ще използваме
алгоритъма на Дейкстра (Dijkstra) за намиране на път от един връх на граф до
всички останали. Смятам, че този алгоритъм ви е добре познат и затова няма
да го описвам. За целта на задачата, обаче, ще изменим малко алгоритъма като
в началото ще маркираме като достигнати всички върхове от околовръстното (а
не само един начален както е в стандартния алгоритъм.) По този начин ние все
едно сме добавили един връх, на разстояние 0 от околовръстните и без връзка
с останалите. Това, което остава е да съберем получените разстояния.
Искам да обърна внимание на факта, че тези минимални разстояния за извоз-
ване на снега се достигат. За да освободим едно "затапено" кръстовище, доста-
тъчно е да освободим постепенно всички по вече открития най-пряк път за из-
возване.
Т.е. спокойно можем да избегнем проблема като освобождаваме първо кръстовища-
та, които са на разсточние 1 улица от околовръстното, после на 2 и т.н.
Мартин Русков
*/
#include <stdio.h>
#define MAX_N 500
#define INFINITY ~0
#define NOT_REACHED 0
#define REACHED 1
#define PASSED 2
#define IN_ROUND REACHED
#define d(a,b,c) (a.x*b.y+b.x*c.y+c.x*a.y-a.x*c.y-c.x*b.y-b.x*a.y)
#define cmp( a, b ) (a.x == b.x && a.y == b.y ? 1 : 0)
typedef struct { int x, y; } vertex;
unsigned n = 6, m = 9;
vertex a[MAX_N] = {{ 0, 6 }, { 0, 2 }, { -2, -1 }, { -4, -3 }, { 3, -2 }, { 5, -3 }};
unsigned link[MAX_N][MAX_N] =
{{ 0, 10, 0, 11, 0, 13 },
{ 10, 0, 6, 0, 9, 0 },
{ 0, 6, 0, 4, 2, 0 },
{ 11, 0, 4, 0, 0, 12 },
{ 0, 9, 2, 0, 0, 1 },
{ 13, 0, 0, 12, 1, 0 }};
unsigned state[MAX_N];
unsigned dist[MAX_N];
void warp( void )
{
vertex x;
int i, j;
for( i = 1, x = a[0]; i < n; i++ )
if( a[i].x > x.x ) j = i;
x = a[j], state[j] = IN_ROUND;
for(;;)
{
if( !cmp( x, a[0] ) )
j = 0;
else
j = 1;
for( i = 0; i < n; i++ )
if( !cmp( a[i], a[j] ) && !cmp( a[i], x ) && d( x, a[j], a[i] ) < 0 )
j = i;
if( state[j] == IN_ROUND ) break;
state[j] = IN_ROUND, x = a[j];
}
return;
}
int done( void )
{
unsigned i;
for( i = 0; i < n; i++ )
if( state[i] != PASSED ) return 0;
return 1;
}
void dijkstra( void )
{
unsigned i, min;
dist[n] = INFINITY;
do
{
for( i = 0, min = n; i < n; i++ )
if( state[i] == REACHED && dist[i] < dist[min] )
min = i;
state[min] = PASSED;
for( i = 0; i < n; i++ )
if( link[min][i] && link[min][i] + dist[min] < dist[i] )
dist[i] = link[min][i] + dist[min], state[i] = REACHED;
}
while( !done() );
return;
}
int main( void )
{
int i, k, l;
warp();
for( i = 0; i < n; dist[i] = state[i] == IN_ROUND ? 0 : INFINITY, i++ );
dijkstra();
for( i = k = 0; i < n; k += dist[i++] );
printf( "%d", k );
return 0;
}