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

Автор aangairbender, 10 лет назад, По-русски

Здравствуйте, уважаемые знатоки =)
Есть такая задача: дано N точек, N <= 2000; нужно найти трегульник максимальной площади, вершинами которого есть 3 и тех N точек. (Точки уже образуют выпуклый многоугольник и заданы в порядке обхода).
У меня 90/100 баллов.(Решал перебором вершины, а остальные две — двумя указателями).
Хотелось бы услышать советы и желательно код.
P.S.: идея у меня вроде правильная, но вот руки... =D

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

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

Читаю заголовок — понимаю, что человеку интересно знать решение задачи или что-то уточнить. Читаю пост, и понимаю, что человек знает решение, да и к тому же рассказал его в посте. Дальше понимаю, что проблема в другом — в коде. А кода нет...

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

    Так-то оно и есть)) Ищу человека, который писал подобное.

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

      Ну ок. Но в посте просятся советы, дам один. Понятно как решать задачу за куб. И ошибиться там негде. Напиши стресс-тест.

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

        Да у меня быдлокод, там что-то убери и все работать не будет :) Вот я и хочу чистую красивую реализацию увидеть. Этот метод(2 указателя) — вообще очень интересная тема.

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

N^2 * log(N) заходит?

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

    Думаю, что да. Ты хочешь перебрать пару(вершини при основе), а потом тернарник запустить, чтоб 3-ую вершину найти(которая будет образовывать макс. высоту треугольника)?

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

Извиняюсь за оффтоп, но как вонимать вот это: 8568517, 8572637?

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

    У меня был плохой день... =) Теперь я уже вырос и не делаю подобных вещей. Да и по правилам КФ ты не должен вылаживать свой код в интернет во время соренования(себя ты тоже спалил).

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится -6 Проголосовать: не нравится

      Интересно, куда же я его выложил?)

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

        Интересно, откуда же я его взял?

        • »
          »
          »
          »
          »
          10 лет назад, # ^ |
            Проголосовать: нравится -11 Проголосовать: не нравится

          Мне тоже это интересно)

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

            pastebin.ru Ты выложил и не знаешь об этом? Может, ты сам его оттуда взял? =)

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

              Боже, что ты несешь... Будь так добр предъявить пруф

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

                И без пруфов понятно, что если у двух человек во время соревнования сдан одинаковый код — значит либо один дал свой код второму, либо им обоим дал код кто-то третий

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

      Может все-таки выкладывать?

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

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

Возможно, здесь же есть решение за . Кажется, что вторую и третью точку можно подбирать тернарниками, если правильно разбить на отрезки (интуитивная оценка: расстояние до самой удаленной точки вдоль прямой выпукло относительно угла; площадь треугольника есть произведение двух таких расстояний и тоже выпукло; не проверял).