Паблик ВКонтакте "типичный программист" организовал контест: объявление.
Призов пока нет, а условия не вычитаны, но все равно какие-то задачи могут показаться интересными. До конца контеста осталось меньше суток, так что желающие поучаствовать должны поторопиться:)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3792 |
| 2 | VivaciousAubergine | 3647 |
| 3 | Kevin114514 | 3603 |
| 4 | jiangly | 3583 |
| 5 | strapple | 3515 |
| 6 | tourist | 3470 |
| 7 | dXqwq | 3436 |
| 8 | Radewoosh | 3415 |
| 9 | Otomachi_Una | 3413 |
| 10 | Um_nik | 3376 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 157 |
| 2 | adamant | 153 |
| 3 | Um_nik | 146 |
| 3 | Proof_by_QED | 146 |
| 5 | Dominater069 | 145 |
| 6 | errorgorn | 141 |
| 7 | cry | 139 |
| 8 | YuukiS | 135 |
| 9 | TheScrasse | 134 |
| 10 | chromate00 | 133 |
Вроде закончилось. Как решать D? И в E надо было просто найти радиус вписанной окружности, или нет?
В D я написал тупой перебор, который где-то за час посчитал все ответы:)
Вписанная в невыпуклый многоугольник окружность это что-то странное... Кто-нибудь умеет, кстати, Е решать?
Короч у них многоугольник выпуклый на самом деле, а клар о невыпуклости был бредом.Кстати, а может все-таки он невыпуклый? А то мои решения, которое считают его выпуклым получают WA1. По-моему, у них слабые тесты, и решение, которое зашло с тернарным поиском случайно нашло тот максимум, который отвечает за самую большую окружность...
Кажется, и правда в первом тесте невыпуклый. Ничего не понимаю, что у них творится.
А что тогда наши тернарники ничего не находят?
Ну тернарник же можно по-разному написать... Например, можно перебирать х, а внутри у, можно наоборот. Можно поставить другие границы поиска и т. д.
Это просто Epic Fail. Их авторское решение — точная копипаста алгоритма с e-maxx для выпуклого многоугольника.
У меня за 4 минуты D посчиталась=)
D — прекальк.
E — да, надо было найти наибольший радиус вписанной окружности, но что-то это непросто. Такая задача уже была в контесте CPR system trial round на snarknews, но там кажется ограничения меньше были. Вот, например, идея решения Жукова: http://mirror.codeforces.com/blog/entry/3632#comment-74188. Но при N <= 10000 работать такое видимо не будет (если я правильно понял, что "Ищем попарные пересечения всего со всем" дает квадрат).
Условия не читал, но вписанную в выпуклый многоугольник окружность можно находить так или так.
В условии не было сказано, что он выпуклый, а потом еще и клар прислали, что может быть невыпуклым (но тут говорят, что это неправда)...
Вообще я вот что нагуглил http://prografix.narod.ru/rus_maxcirn.html , но там просто адова куча исходников и разбираться в них влом. Работает или нет, хз.
А соревнование уже закончилось? Я никак условия найти не могу.
Закончилось, условия можно посмотреть в e-judge после того, как зарегистрировался и вошел в систему.
Я даже после того как прочитал
ту пдфкутексты, похожие на шесть задач, все равно не смог найти условий.UPD: их, кстати, нельзя просмотреть когда контест в режиме OVER
Если что, то уже можно посмотреть [и даже дорешивать].
Зеленые школьники решили прославить себя на весь контактик: подняли еджадж, взяли откуда-то задачи и устроили контест с кучей багов. Круто.
"Указывайте, пожалуйста имена или ники, чтобы мы могли знать, кто же лучший!"
Я знаю что не лучший, поэтому не укажу:)
Кстати F(последняя) походит на вторую с Facebook Round 2, только проще.
UPD: комент не туда.
Скиньте ссылку на условия, пожалуйста.
UPD. Не нужно, спасибо.