[shkola] Malko poqsneniq

Za tezi nenadareni s prorocheski sposobnosti (i ne chetqshti edin drug
maillist) malko razasneniq za posledniq post na Ljudo. Dolu e citiran mail na
Ivo.

=======================
> imate x,y,z koordinati na tochki. Da se nameri sferata koiato e s nai
> malak radius i obhvasta vsicki (3 kont. 2001)

Ostawqm nastrana trimernata zadacha. Shte wi razkazha za 2D, pxk kojto
iska da si adaptira resheniqta.

> imate x,y koordinati na tochki. Da se nameri kragcheto s nai malak
> radius obhvastast vsicki tochki
> (BOI 2002)

Napisah edno reshenie - hwana 8 ot 10 testa. W posledstwie poglednah i
reshenieto na Welin Tzanov. Pochti ednakwo e s izkljuchenie na edin
moment...

Moqta udeq e:
Pxrwo prawish izpxknalata obwiwka. Towa predpolagam che ste se setili.
Sled towa namirash naj-golemiqt diagonal(ili strana) w polucheniq
izpxknal mnogoxgxlnik. Namirash dwata wxrha, koito opredelqt tozi
diagonal i takxw treti wrxh, pod koito diagonala se wizhda pod
naj-malxk xgxl. Spored men opisanata okolo tozi trixgxlnik okr. she
opishe i mnogoxgxlnika. Towa e wqrno, obache qwno w nqkoi testowe towa
ne e naj-optimalnoto reshenie.

Ideqta na Welin e slednata:
1. Izpxknala obwiwka.
2. Wzimash pxrwite dwa wxrha. I namirash takxw treti, pod kojto
otsechkata se wizhda pod naj-malxk xgxl.
3. Sega ako polucheniqt trixgxlnik ne e txpoxgxlen, to toj e
txrseniqt(!?! - az li ne mu razbiram source-a ili naistina tuk e
kljuchowiqt moment za optimalnost. Tuk e i edinstwenata razlika s moqt
algoritxm).
4. Ako ne e, to se wrxshtash na 2, kato za nowata otsechka izpolzwash
naj-dxlgata strana na namereniqt txpoxgxlen trixgxlnik.

Sredanata slozhnost i pri dwata algoritxma e N*log(N). Idwa ot
izpxknalata obwiwka.
======================

Reshenieto na Canov predpolagam mozhe da se nameri v stari broeve na
infoman. Ivo ako iskash prati i tvoeto reshenie.

-- 
Rangel Dokov

Other related posts: