Первая личная интернет-олимпиада.

11 лет назад, # |

Как решать D на 100?

→ Ответить

11 лет назад, # ^ |

Епсилон — вроде такая малость, а иногда 90 баллов стоит. Скачал тесты, поправил, протестил и заработало такое вот:

Обрабатываем эти треугольники в том порядке, в котором даны. Для текущего треугольника смотрим — задействовались ли его стороны в более ранних треугольниках (это можно делать, например, map-ом) — если да, то строим по нашему текущему описанную окружность и проверяем расстояние до третей вершины каждого такого раннего треугольника. Из условия каждая сторона может быть задействована лишь в двух треугольниках.

Строгого доказательства не дам.

→ Ответить

11 лет назад, # ^ |

Я так понимаю, получается все тот же квадрат, но с меньшей константой.

→ Ответить

11 лет назад, # ^ |

Получается не квадрат, потому что для каждого треугольника проверять придётся максимум 3 точки, по одной для каждой стороны

→ Ответить

11 лет назад, # ^ |

← Rev. 4 →

Хотя все таки нет. Если я правильно понял, то если точка из "раннего" треугольника окажется вне окружности, а точка из не "раннего" окажется внутри, то все плохо.

→ Ответить

Miras321

11 лет назад, # ^ |

Если точка из не "раннего" треугольника внутри, значит пересекаются две окружности. Даже если мы пропустим пару "А пересекает Б", то мы обязательно обработаем "Б пересекает А".

→ Ответить

11 лет назад, # ^ |

А как это учитывает одиночные точки?

→ Ответить

11 лет назад, # ^ |

Эмм, простите? Я не очень понял

Если речь о том, что будет где-то стоять точка, к которой ни одного ребра не проведено, то таких не будет, так как формально у нас дана триангуляция выпуклого многоугольника, только тогда суммарная площадь ловушек максимальна (как говорится в конце второго абзаца)

→ Ответить

11 лет назад, # ^ |

Понял, спасибо. А какой у тебя eps был?

→ Ответить

http://www.ict.edu.ru/ft/004503/09.pdf

11 лет назад, # ^ |

Пожалуйста

Вообще 1e-9, это заходит. Проблема была не в размере eps, а в его отсутствии в паре мест

→ Ответить

Alex_2oo8

11 лет назад, # ^ |

+13

Страница 10, теорема 1 и Страница 20 дают решение в целых числах на 100 баллов.

→ Ответить

I_love_natalia

11 лет назад, # ^ |

В целых числах принадлежность точки окружности через заданные три проверять углами немного лень, т.к. можно написать double + long проверку на 30 десятичных разрядов. Пишем окружность через три точки, смотрим знак в даблах, если по модулю меньше 10^18 считаем в long long.

→ Ответить

11 лет назад, # |

+18

Большая просьба к жюри : отвечайте, пожалуйста, на вопросы участников. Я отправил вопрос на [email protected] через полчаса после начала олимпиады по поводу регистра букв в задаче B. Ответ не пришел, но где-то на втором часу олимпиады изменили pdf-файл с условиями, где говорилось, что буквы строчные, однако клара об этом не было.

→ Ответить

Mediocrity

11 лет назад, # ^ |

Мне ответили.

→ Ответить

11 лет назад, # ^ |

Повезло)

→ Ответить