Блог пользователя moskalenco_a

Геометрия
Автор moskalenco_a, история, 9 лет назад, По-русски

Всем привет. Решаю несложную геометрию. Решаю вот как: считываю xi, yi, составляю уравнение прямой которое проходит через x0, y0, xi, yi пользуясь формулой (x — x1) / (x2 — x1) = (y — y1) / (y2 — y1). И добавляю уравнение в множество (std::set). И потом просто вывожу размер множества. Коэффициенты прямой храню в виде пар чисел которые представляют несократимую дробь. К сожалению на 8 тесте получаю WA. Где может быть баг? 16591043

  • Проголосовать: нравится
  • +11
  • Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Легче:

Подумайте, что различает все ваши прямые, когда вы строите их по "школьному" уравнению прямой.

→ Ответить
»
9 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Я вот как решил:

Прямую задает однозначно направляющий вектор и точка через которую она проходит. Вычисляем координаты направляющего вектора в double: vx=(x-x0)/mod, vy=(y-y0)/mod где mod=sqrt( sqr(x-x0) + sqr(y-y0) ). Также получаем координаты того же вектора в обратном направлении vx'=-vx, vy'=-vy. Далее слегка загвоздка выходит, т.к вставляя эти две пары координат в set < pair<double,double> > точно выйдет погрешность со сравнением. Поэтому вставляем в pair <int,int> эти пары помноженные на, скажем 1000000000. На ограничениях этой задачи погрешность не случится. И да, ответом будет размер set'a деленный на 2.

→ Ответить
»
9 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Я не понял, зачем при запоминании прямой хранилась вторая пара.

Но если её убрать, это решение проходит.

→ Ответить
  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Кстати, хороший тест для такой задачи — все точки грида в некоторой окрестности, например:

    24 0 0
-2 -2
-2 -1
-2 0
-2 1
-2 2
-1 -2
-1 -1
-1 0
-1 1
-1 2
0 -2
0 -1
0 1
0 2
1 -2
1 -1
1 0
1 1
1 2
2 -2
2 -1
2 0
2 1
2 2

    И руками легко ответ посчитать (8), и ловит баг в исходном решении.

    → Ответить
»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Кстати, вот пожалуй лучшее решение этой задачи за O(N log N) 9838096. Очень просто, странно что я не подумал об этом.

→ Ответить
  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится

    Ну так если в вашем решении убрать b из k x + b и оставить только k, разрешив ему быть нулём, как раз и получается то же самое. Даже короче, потому что gcd сразу правильного знака. Число b не нужно, поскольку все наши прямые проходят через одну точку.

    → Ответить