Сегодня прошла первая личная интернет олимпиада. Предлагаю обсудить задачи здесь.
→ Обратите внимание
До соревнования
Refact.ai Match 1 (Codeforces Round 985)
4 дня
Зарегистрироваться »
Refact.ai Match 1 (Codeforces Round 985)
4 дня
Зарегистрироваться »
*есть доп. регистрация
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3831 |
| 3 | Radewoosh | 3646 |
| 4 | jqdai0815 | 3620 |
| 4 | Benq | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | gamegame | 3386 |
| 10 | ksun48 | 3373 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 164 |
| 1 | maomao90 | 164 |
| 3 | Um_nik | 163 |
| 4 | atcoder_official | 160 |
| 5 | -is-this-fft- | 158 |
| 6 | awoo | 157 |
| 7 | adamant | 156 |
| 8 | TheScrasse | 154 |
| 8 | nor | 154 |
| 10 | Dominater069 | 153 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 05.11.2024 06:48:38 (l2).
Десктопная версия, переключиться на мобильную.
При поддержке
Как решать D на 100?
Епсилон — вроде такая малость, а иногда 90 баллов стоит. Скачал тесты, поправил, протестил и заработало такое вот:
Обрабатываем эти треугольники в том порядке, в котором даны. Для текущего треугольника смотрим — задействовались ли его стороны в более ранних треугольниках (это можно делать, например, map-ом) — если да, то строим по нашему текущему описанную окружность и проверяем расстояние до третей вершины каждого такого раннего треугольника. Из условия каждая сторона может быть задействована лишь в двух треугольниках.
Строгого доказательства не дам.
Я так понимаю, получается все тот же квадрат, но с меньшей константой.
Получается не квадрат, потому что для каждого треугольника проверять придётся максимум 3 точки, по одной для каждой стороны
Хотя все таки нет. Если я правильно понял, то если точка из "раннего" треугольника окажется вне окружности, а точка из не "раннего" окажется внутри, то все плохо.
Если точка из не "раннего" треугольника внутри, значит пересекаются две окружности. Даже если мы пропустим пару "А пересекает Б", то мы обязательно обработаем "Б пересекает А".
А как это учитывает одиночные точки?
Эмм, простите? Я не очень понял
Если речь о том, что будет где-то стоять точка, к которой ни одного ребра не проведено, то таких не будет, так как формально у нас дана триангуляция выпуклого многоугольника, только тогда суммарная площадь ловушек максимальна (как говорится в конце второго абзаца)
Понял, спасибо. А какой у тебя eps был?
Пожалуйста
Вообще 1e-9, это заходит. Проблема была не в размере eps, а в его отсутствии в паре мест
http://www.ict.edu.ru/ft/004503/09.pdf
Страница 10, теорема 1 и Страница 20 дают решение в целых числах на 100 баллов.
В целых числах принадлежность точки окружности через заданные три проверять углами немного лень, т.к. можно написать double + long проверку на 30 десятичных разрядов. Пишем окружность через три точки, смотрим знак в даблах, если по модулю меньше 10^18 считаем в long long.
Большая просьба к жюри : отвечайте, пожалуйста, на вопросы участников. Я отправил вопрос на [email protected] через полчаса после начала олимпиады по поводу регистра букв в задаче B. Ответ не пришел, но где-то на втором часу олимпиады изменили pdf-файл с условиями, где говорилось, что буквы строчные, однако клара об этом не было.
Мне ответили.
Повезло)
И мне :)
Да, нашел ваше письмо во входящих, на него действительно нет ответа. Приношу свои извинения.
Блин, я как сейчас помню что писал про строчные буквы в условии :(
Ну в двух твоих ревизиях условия в формате входных данных этого нет. Я вот помню, что когда первый раз вычитывал — обратил на это внимание, проверил валидатор, а потом забыл дописать >_<
Добавят ли данный контест в тренировки КФ?
Добавил тренировку.
Подскажите, кто-нибудь! На сайте олимпиады выложены тесты, авторские решения. А как можно выложенными чекерами протестировать задачи.И вообще можно ли это сделать. Спасибо.
Вы можете отправить свое решение в тренировку на CodeForces и посмотреть вердикт.
Согласен с Вами. Но, на CF тестируется до первого не пройденного теста. И все-таки можно ли используя чекеры архива олимпиады протестировать задачу?.