[idle] Re: blabla
- From: Ivaylo Riskov <ivaylo_riskov@xxxxxxx>
- To: idle@xxxxxxxxxxxxx
- Date: Wed, 30 Apr 2003 12:26:35 +0300
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:
