[idle] Re: blabla

Bez da wi komentiram bobxra shte mina na dwete zadachi!
Btw, pishete gi w list-a na shkolata. Tuk maj nqmat mqsto.

> 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.

> Kakvo li mi podskazva ce tova im e lubima zadacha :)
Wizh togawa zadachite ot Plovdiv minalata godina za trite grupi. 
Po-skoro e ot mxrzel da mislqt zadachi!

-- 
Ivaylo Riskov <ivaylo_riskov@xxxxxxx>

"How much wood would a woodchuck chuck, 
if a woodchuck would chuck wood?"

Other related posts: