Задачи по программированию.

Discussion in 'С/С++, C#, Rust, Swift, Go, Java, Perl, Ruby' started by Vollkorn, 12 Jun 2011.

  1. Vollkorn

    Vollkorn Member

    Joined:
    6 Nov 2010
    Messages:
    86
    Likes Received:
    15
    Reputations:
    -6
    Привет, народ.)
    У меня вот вопрос возник, решил тут спросить советов.
    Вобщем, как решать задачи, в которых используются координаты? То есть например даны координаты чего-то там, и надо найти что-то там. Принимать ли всё за матрицу, и т.д., помогите пожалуйста.

    Пример задачи:
    Входные данные
    В первой строке входного файла INPUT.TXT находится одно целое число N (количество деревьев) (3 ≤ N ≤ 255). В каждой из последующих N строк записаны два целых числа Xi*и Yi*– координаты очередного дерева в прямоугольной декартовой системе координат (-10000 ≤ Xi,Yi*≤ 10000). Деревья достаточно малы, поэтому их можно считать точками на плоскости. Никакие три дерева не лежат на одной прямой. Числа в строках разделены одним пробелом.
    Выходные данные
    Единственная строка выходного файла OUTPUT.TXT должна содержать одно целое число – количество вариантов выбора участка на которых не будет деревьев. Участок может быть только треугольной формы.

    Заранее спасибо.
     
  2. scrat

    scrat кодер

    Joined:
    8 Apr 2007
    Messages:
    625
    Likes Received:
    541
    Reputations:
    3
    Зависит от задачи. Тут сказано, что никакие три дерева не лежат на одной прямой => образуют треугольник. Значит количество треугольников — это количество сочетаний из N по 3. Хотя я, наверное, ошибаюсь.
     
  3. Fepsis

    Fepsis Elder - Старейшина

    Joined:
    17 Sep 2008
    Messages:
    791
    Likes Received:
    391
    Reputations:
    72
    плюс по каждому треугольнику нужно проверить, нет ли внутри него деревьев...
     
  4. Vollkorn

    Vollkorn Member

    Joined:
    6 Nov 2010
    Messages:
    86
    Likes Received:
    15
    Reputations:
    -6
    Я ж вот и спрашиваю, как это лучше реализовать?)
    Принимать ли всё за матрицу, и там как-то пытаться, или нет? Или как лучше?
     
  5. sn0w

    sn0w Статус пользователя:

    Joined:
    26 Jul 2005
    Messages:
    1,021
    Likes Received:
    1,189
    Reputations:
    327
    сперва нужно написать координатный интерпретатор под x86 и IA64 и x64. затем нужно написать препроцессор деревьев и компилятор точек. и в конце - генератор единственной строки в единственном файле, конечно же с учетом va_list
     
  6. scrat

    scrat кодер

    Joined:
    8 Apr 2007
    Messages:
    625
    Likes Received:
    541
    Reputations:
    3
    Fepsis, да, точно, про такой случай я и забыл. :)

    Ссылки по теме:
    http://forum.codenet.ru/threads/40874
    http://algolist.manual.ru/maths/geom/belong/poly2d.php

    только блин сложность n^3 получается :(

    Если я правильно понял:
    [​IMG]
     
    #6 scrat, 13 Jun 2011
    Last edited: 13 Jun 2011
    1 person likes this.
  7. cheater_man

    cheater_man Member

    Joined:
    13 Nov 2009
    Messages:
    651
    Likes Received:
    44
    Reputations:
    7
    Это же очень муторно=)
    Пиши как знаешь=)
     
  8. Vollkorn

    Vollkorn Member

    Joined:
    6 Nov 2010
    Messages:
    86
    Likes Received:
    15
    Reputations:
    -6
    Всем спасибо)
     
  9. St0nX

    St0nX Elder - Старейшина

    Joined:
    19 May 2007
    Messages:
    257
    Likes Received:
    46
    Reputations:
    0
    Используй триангуляцию делоне. Если конечно я правильно понял суть задачи. Алгоритм "разделяй и властвуй" nlogn на деление + nlogn на слияние.
     
Loading...