MikhailRubinchik.ru's blog

By MikhailRubinchik.ru, 7 years ago, In Russian,

В русскоязычном АСМ ICPC часто ругаются на геометрию. Её мало кто любит писать. Все всегда боятся за неё браться.

Как ни странно, на Урале геометрию любят. Я сам всегда во всех командах отвечал за геометрию (ещё со школы). И мне приятней всего на соревнованиях писать именно её.

Я в девятом классе начал тренироваться у goryinyich. Соответственно, первые уроки получил у него. Далее читал лекции Андреевой, потом Кормена. Что-то доводил сам. Позже интересные идеи узнавал от разных олимпиадников урала. В частности немало почерпнул в исходниках Stigius и winger.

Основная проблема, на мой взгляд в том, что нет ни одной статьи в олимпиадном движении, где собраны все геометрические примитивы.

Очень часто все геометрические задачи тут же сводят к алгебре, что мешает восприятию геометрических образов. На e-maxx.ru вообще толком ничего не реализовано. А то, что реализовано, сделано не пойми как.

Цель данного поста увидеть реакцию сообщества на мой код, возможно получить какую-то хорошую критику и доработку кода. Ну и в итоге добавить в какой-то публичный источник. Например, на e-maxx.ru

Соответственно к читающим вопросы: 1. Что из того, что здесь не реализовано, вам приходилось использовать?

  1. Что из того, что реализовано здесь, вы делаете совершенно по-другому и как?

  2. Ну и указывайте на ошибки, если видите :) Код не тестирован, но я всегда его пишу практически одинаково.

P.S. Скоро доделаю комментарии и к 3d версии и выложу и её.

2d Геометрия

3d Геометрия

UPD: Убрал код из статьи

UPD2: Добавил 3d

Интересные места в 3d:

  1. Поворот в 3d почти не отличается от поворота в 2d (я не использую сущность "матрица" для поворота)

  2. на мой взгляд стоит обратить внимание на пересечение двух плоскостей. Мне в своё время эта идея показалась интересной.

  3. И интересный момент, что пересечение прямых в 2d преобразуется совсем маленькими изменениями в пересечение прямых в 3d и пересечения прямой и плоскости в 3d

 
 
 
 
  • Vote: I like it
  • +96
  • Vote: I do not like it