Привет, народ.) У меня вот вопрос возник, решил тут спросить советов. Вобщем, как решать задачи, в которых используются координаты? То есть например даны координаты чего-то там, и надо найти что-то там. Принимать ли всё за матрицу, и т.д., помогите пожалуйста. Пример задачи: Входные данные В первой строке входного файла INPUT.TXT находится одно целое число N (количество деревьев) (3 ≤ N ≤ 255). В каждой из последующих N строк записаны два целых числа Xi*и Yi*– координаты очередного дерева в прямоугольной декартовой системе координат (-10000 ≤ Xi,Yi*≤ 10000). Деревья достаточно малы, поэтому их можно считать точками на плоскости. Никакие три дерева не лежат на одной прямой. Числа в строках разделены одним пробелом. Выходные данные Единственная строка выходного файла OUTPUT.TXT должна содержать одно целое число – количество вариантов выбора участка на которых не будет деревьев. Участок может быть только треугольной формы. Заранее спасибо.
Зависит от задачи. Тут сказано, что никакие три дерева не лежат на одной прямой => образуют треугольник. Значит количество треугольников — это количество сочетаний из N по 3. Хотя я, наверное, ошибаюсь.
Я ж вот и спрашиваю, как это лучше реализовать?) Принимать ли всё за матрицу, и там как-то пытаться, или нет? Или как лучше?
сперва нужно написать координатный интерпретатор под x86 и IA64 и x64. затем нужно написать препроцессор деревьев и компилятор точек. и в конце - генератор единственной строки в единственном файле, конечно же с учетом va_list
Fepsis, да, точно, про такой случай я и забыл. Ссылки по теме: http://forum.codenet.ru/threads/40874 http://algolist.manual.ru/maths/geom/belong/poly2d.php только блин сложность n^3 получается Если я правильно понял:
Используй триангуляцию делоне. Если конечно я правильно понял суть задачи. Алгоритм "разделяй и властвуй" nlogn на деление + nlogn на слияние.