Hide

Problem S
Striker-Count

Eitt gott vorkvöld var Bergur að spila Striker-Count. Hann er mjög góður í Striker-Count og vinnur andstæðinga sína yfirleitt algjörlega fyrirhafnarlaust. Því er hann farinn að pæla í því hvernig hann getur sigrað andstæðinga sína með stæl. Hann ákveður því að hann ætlar að hoppa upp í loftið, snúa sér í heilan hring og skjóta svo einu skoti með sínum trausta PWA. En hann fer að velta því fyrir sér, hver er mesti fjölda andstæðinga sem hann getur hitt með þessum hætti?

Við lítum svo á að Bergur sé staddur í núllpunkt hnitakerfis. Andstæðingar hans eru gefnir sem miðja hrings einhverstaðar í hnitakerfinu og geisla á þeim hring. Þá er eitt skot geisli útfrá núllpunkti og hittir það andstæðing þ.þ.a.a. geislinn skeri hringinn, ekki dugar að snerta hann. Gefið er að enginn andstæðingur innihaldi Berg. Hins vegar geta þeir skarast ef þeir standa ofan á hvorum öðrum. Þar sem Bergur er svo einstaklega góður í Striker-Count þá hittar hann samt báða ef geislinn sker báða hringina.

Inntak

Fyrsta línan er heiltala $n$ þ.a. $1 \leq n \leq 10^5$ sem er fjöldi andstæðinga Bergs. Svo fylgja $n$ línur, hver með fleytitölum $x, y, r$ þ.a. $-10^9 \leq x, y \leq 10^9$, $0 < r \leq 10^9$ sem segja að líta má á þann andstæðing sem hring með miðju $(x, y)$ og geisla $r$. Allar fleytitölur munu hafa mest sex kommustafi. Það er tryggt að til sé grennd með geisla $10^{-9}$ um stefnuhorn lausnar þannig að öll horn í grenndinni gefa sama svar.

Úttak

Eina heiltölu $k$, hámarksfjölda andstæðinga sem Bergur getur hitt með einu skoti.

Sample Input 1 Sample Output 1
5
5 0 1
10 0 1
0 5 1
0 -5 1
-5 0 1
2
Sample Input 2 Sample Output 2
6
2 2 2
6 2 1
10 2 1
2 6 1
6 6 1
2 10 1
3

Please log in to submit a solution to this problem

Log in