Tävlingsprogrammering/Uppgifter/Vakttorn

Vakttorn

FIGUR 3. Punkterna visar de viktiga platserna i exemplet och kryssen visar en möjlig placering av de tre vakttornen för att kunna bevaka sju platser. Torn 1 övervakar punkterna 4 och 10, torn 2 övervakar punkterna 7 och 8, och torn 3 övervakar punkterna 2, 5 och 6.

Du önskar bygga tre vakttorn med varierande höjd för att övervaka ett antal viktiga platser. Skriv ett program som, givet koordinaterna på platserna du vill övervaka, samt hur långt du kan se från vart och ett av tornen, bestämmer var tornen ska placeras så att så många platser som möjligt kan övervakas från åtminstone ett torn. Tornen kan placeras varsomhelst på xy-planet, inklusive på en plats som önskas övervakas.

Rent formellt kan både platserna och tornen betraktas som punkter i xy-planet. Om det euklidiska avståndet mellan ett torn och en punkt inte överskrider tornets betraktningsavstånd kan punkten övervakas.

Första raden i filen vakttorn.dat innehåller en rad med ett tal N (1 ≤ N ≤ 40), antalet punkter du vill övervaka. Därefter följer en rad med tre heltal som anger betraktningsavstånden från vart och ett av tornen (1 ≤ h[i] ≤ 1000). Sedan följer N rader som anger koordinaterna för var och en av punkterna du vill övervaka. Alla koordinater är heltal mellan 0 och 1000. Två punkter har aldrig samma koordinater.

Skriv ut det maximala antalet punkter som kan övervakas om tornen placeras optimalt, samt ge ett exempel på var tornen ska placeras för att realisera detta. Notera att tornen inte nödvändigtvis behöver placeras på heltalskoordinater (3 decimaler är tillräckligt i utskriften).

Körningsexempel: Filen vakttorn.dat med innehållet

kan ge svaret

Platser som kan övervakas: 7 
Torn 1: 9, 15
Torn 2: 4, 12
Torn 3: 18.5, 15.25

Observera att det finns andra placeringar som ger samma antal övervakade platser.

Lösning

Detta var den klart svåraste uppgiften i PO-finalen 2009.

Första steget i lösningen är att ta fram kandidatplatser för varje vakttorn. Vi betraktar således ett vakttorn (en cirkel med en viss radie) i taget.

Om ett vakttorn täcker in två eller fler punkter går det alltid att placera den cirkeln så att två av punkterna innanför cirkeln hamnar på cirkelns kant genom att förskjuta cirkeln åt något håll. Vi kan på så sätt generera kandidatpunkter genom att loopa över varje par av punkter och beräkna var en cirkel med en viss radie måste vara för att dessa två punkter ska hamna på kanten av cirkeln. Generellt sätt finns det två sätt att placera en cirkel så att punkterna hamnar på kanten. Centrum för cirkeln kan beräkna på lite olika sätt, men enklast är att använda vektormatematik:

// Indata:
// x[i],y[i] = den ena punkten
// x[j],y[j] = den andra punkten
// radius    = radien på cirkeln

// Första beräknar vi vektorn från punkt i till mittpunkten mellan de båda punkterna
double vx = (x[j] - x[i]) / 2.0, vy = (y[j] - y[i]) / 2.0;

// Sedan den normaliserade vektor som är ortogonal mot vektorn som går mellan punkterna
double px = -vy, py = vx;
double plen = Math.Sqrt(px * px + py * py);
px /= plen;
py /= plen;

// Beräkna med Pythagoras sats hur lång den ortogonala vektorn ska vara
double vlen = Math.Sqrt(vx * vx + vy * vy);
var d = radius * radius - vlen * vlen;

// Om avståndet mellan punkterna är exakt lika som radien på cirkeln kan
// det uppstå avrundningsproblem. Dessa fixar vi till med följande rad.
if (Math.Abs(view[k] - vlen) < 1e-6)
{
	d = 0;
}

// Om d nu är negativt innebär det att avståndet mellan punkterna är längre än cirkelns diameter,
// i vilket fall cirkeln inte kan täcka in båda punkterna.
// Här antar vi att vi har gjort den kollen tidigare i koden någonstans.
plen = Math.Sqrt(d);
px *= plen;
py *= plen;

// Beräkna de två möjliga centerkoordinatern för en cirkel vars avstånd 
// till de båda punkterna är exakt radius.
double x1 = x[i] + vx + px, y1 = y[i] + vy + py;
double x2 = x[i] + vx - px, y2 = y[i] + vy - py;

Detta kommer att ta fram O(N^2) kandidatplatser per vakttorn. Däremot missar vi alla kandidatplatser som täcker in endast en punkt. Därför måste vi även lägga till som kandidatplatser alla punkter i indata. Fortfarande är det O(N^2) kandidatplatser.

Nästa steg är att eliminera onödiga kandidatplatser. Om en kandidatplats i täcker in samma mängd punkter som en annan kandidatplats j plus eventuellt ytterligare några, finns det förstås ingen poäng med att placera ett vakttorn vid j eftersom ett vid i skulle täcka in samma punkter (eller fler).

Det visar sig att denna eliminering är mycket effektiv. Om det i indata fanns 40 punkter (vilket var maxgränsen), kommer vi i worst case ha ca 800 kandidatplatser. Men efter denna eliminering kommer mindre än 100 punkter finnas kvar! Att det blir så är inte helt uppenbart på förhand, utan kräver lite "känsla" för 2D-geometri.

Nu återstår sista steget, att testa alla kandidatplatser. För varje vakttorn har vi, som sagts ovan, max ca 100 kandidatplatser. Därför kan vi helt enkelt göra tre nästlade loopar som testar alla kombinationer av kandidatplatser för vakttornen. Det kommer max finnas ca 100*100*100 sådana kombinationer, vilket är ingenting för dagens datorer. För varje kombination kollar vi hur många av punkterna som täcks in (ytterligare en loop till max 40, men fortfarande inget problem), och sparar undan den kombination som ger bäst täckning.