C. Буудлагын талбай

хугацааны хязгаарлалт 2 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Нэгэн нарлаг өдөр Копа хаан төв цэнгэлдэх хүрээлэнд байрлах буудлагын талбайд зочлон гол шагнал болох том ягаан баавгайг хожихоор шийджээ. Хаан буудлагад нэг их сайн биш болохоор таныг туслуулахаар урьжээ.

Буудлагын талбар нь тэгш өнцөгт координатын систем бүхий хязгааргүй босоо хавтгай юм. Бай нь энэ хавтгай дээр байрлах цэг юм. Бай болгоны мэдээлэлд $x_{i}$, $y_{i}$ координатууд, $t_{i}$ хугацаа буюу байн гарж ирэх мөч, $p_{i}$ магадлал буюу Копа байг онилох үед онох магадлал гэх мэдээллүүд багтах юм.

Бай эгшин зуур гарч ирэн буцаад алга болно. Тиймээс Копагийн бууны онио зөвхөн $t_{i}$ мөчид $(x_{i}, y_{i})$ координат дээр онилж байвал байг онох боломжтой. Хавтгай дээрх бууны онионы хөдлөх хурд $1$-тэй тэнцүү. Копа буудаж эхлэхийн өмнө бүх байны мэдээллийг мэдэж байгаа (түүнийг хаан гэдгийг сана). Хаан хамгийн олон байг онох тохиромжтой аргаар тоглож байгаа. Хаан $0$ мөчид дурын газарт онилох боломжтой.

Оролт

Эхний мөрөнд буудлагын талбарт байх нийт байны тоо буюу $n$ ($1 ≤ n ≤ 1000$) бүхэл тоо өгөгдөнө. Дараагийн $n$ мөрөнд бай болгоныг тайлбарласан $4$ тоо $x_{i}$, $y_{i}$, $t_{i}$, $p_{i}$ (энд $x_{i}$, $y_{i}$, $t_{i}$ нь бүхэл тоо, $-1000 ≤ x_{i}, y_{i} ≤ 1000, 0 ≤ t_{i} ≤ 10^{9}$, болон $p_{i}$, $0 ≤ p_{i} ≤ 1$ тоо нь таслалын араас $6$-аас ихгүй оронгоор өгөгдөнө) өгөгдөнө. Аль ч $2$ бай нэг цэг дээр байрлахгүй.

Гаралт

Хааны онож чадах байн боломжит хамгийн их оноог хэвлэнэ. Хэрвээ таны хариу зөв хариунаас $10^{-6}$-аас ихгүйгээр зөрвөл таны хариуг зөвшөөрнө.

Орчуулсан: Энхлут

Жишээ тэстүүд

Оролт
1
0 0 0 0.5
Гаралт
0.5000000000
Оролт
2
0 0 0 0.6
5 0 5 0.7
Гаралт
1.3000000000
Сэтгэгдлүүдийг ачааллаж байна...