Задача о триангуляции многоугольника

Задан многоугольник координатами своих вершин вдоль обхода его контура. Требуется указать множество непересекающихся во внутренних точках диагоналей, разбивающих многоугольник на треугольники. Вход: файл input.txt, , в первой строке которого записано число N – количество вершин многоугольника, потом в N строках пары целых чисел – координат вершин многоугольника в порядке обхода контура. Ограничения: 4 ≤ N ≤ 200; каждая координата от -10000 до 10000 Выход: файл output.txt, в первой строке которого должно быть число k, указывающее необходимое число диагоналей. В последующих k строках должно быть по два натуральных числа – номер начальной и конечной вершины соответствующей диагонали. Дополнительные ограничения: диагонали должны лежать строго внутри многоугольника (все точки диагонали, за исключением концов, являются внутренними точками многоугольника). Пример: input.txt 5 1 1 2 5 5 5 5 1 2 2
output.txt 2 2 5 3 5 Мое решение: Количество диагоналей равно (количество вершин - 3) Соединяем все точки от (2) до (количество вершин - 2) с последней точкой; если прямая между соединяемой и последней точкой лежит вне многоугольника (многоугольник невыпуклый), то берем следующую точку и соединяем ее с некоторыми (какими?) точками. Помогите, пожалуйста, все это реализовать или подскажите, как проверить принадлежность прямой (или точки) многоугольнику и какие точки соединять, если многоугольник является невыпуклым.

Ответ

Если число вершин <= 3 разбиение закончено Выбраем первую вершину как текущую (N) Если из неё нельзя провести диагональ внутри многоугольника к точке N+2, то теущей становится следующая и т.д. по кольцу. Думаю можно доказать, что этот цикл не бесконечен. "Отрезаем" треугольник от многоугольника, вершин становится на одну меньше за счёт исключения вершины N+1. Переходим к пункту 1
Наверно удобно использовать связный список.
Определение проходит ли диагональ внутри многоугольника.
Заранее определим в каком направлении задан многоугольник - по или против часовой стрелки. Далее если треугольник N N+1 N+2 обходится в противоположном направлении, значит наша диагональ снаружи - не подходит. В противном случае возможен ещё вариант когда диагональ оказывается снаружи полностью или частично по вине других внутренних углов, это проверяется далее.
Для точек N+3 и N-1 нужно проверить, чтобы эти углы при этих вершинах были больше чем соответствующие углы отрезаемого треугольника. Т.е. вершина лежит по другую сторону от диагонали относительно вершины N+1, либо угол при вершине больше развёрнутого. (См. на картинке для вершины 2 угол 2-3-1 больше чем 2-3-4, или 4 и 2 находятся по одну сторону от диагонали 3-1, поэтому диагональ 3-1 не подходит. Для вершины 8 она с вершиной 6 по одну сторону диагонали 7-1, но угол 7 больше развёрнутого, поэтому это не мешает, вершина подходит.)
Для оставшихся сторон нужно проверить не пересекают ли они данную диагональ. (Например на рисунке сторона 6-7 пересекает диагональ 4-2. Точка пересечения прямых принадлежит отрезку.) Тут четыре стороны проверять не нужно: это стороны при вершине и соседние к ним.
Определение направления обхода многоугольника
Проводим из одной вершины A1 вектора ко всем остальным A1->A2, A1->A3, ... A1->AN. Считаем сумму N-1 векторных произведений соседних векторов по порядку, нас интереует только координата z. Эта сумма по модулю равна удвоенной площади фигуры, а знак указывает направление обхода.
Оптимизация от @AnT: Для того, чтобы определить направление обхода многоугольника достаточно вычислить векторное произведение сторон инцидентных с нижней-левой вершиной (минимальный x среди минимальных y). Делать это во всех вершинах (т.е. считать полную площадь) нет никакой необходимости.
Иллюстрация к случаям рассмотренным в алгоритме.

Как делается такая менюшка как вконтакте

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

Вот так не должно быть
(тут смена цвета шрифта происходит только после анимации)

Ответ

Да в общем ничего сложного. Если схеметически описать, то это примерно так: $('selector').click(function(){ $('blok_with_blue_bg').animate({ left: position_of_active_element }, function(){ // это callback-функция, которая выполняется после завершения анимации $('active_element').css('color','new_color'); }); }); P.S. Чтоб было более понятно, я набросал вам простенький пример UPD Может не на все 100% так же, как на ВК, но на 95% так точно. Смотрите то, что получилось. Сделал анимацию помедленней, чтоб вам опять не пришлось скрины делать ))

SQL-запрос, выводящий max(count(…)) и другие поля таблицы, соответствующие max-параметру

Имеются следующие таблицы: Person(поля Nom и др.) - информация о людях, Profit(поля ID, Source, Moneys) - источники дохода, Have_d(поля Nom, ID и др.) - связь между людьми и их доходами. Каждый человек может иметь несколько источников дохода. Необходимо вывести всю информацию о самом популярном источнике дохода. То есть необходимо подсчитать количество включений всех видов доходов, выбрать максимальное и вывести полученное число вместе со всеми полями таблицы Profit, соответствующими полученному максимуму. Я смогла вывести максимальное число, но не получается составить запрос на вывод строки из Profit, ему соответствующей. select max(expr1) from (select count(nom) as expr1 from profit, have_d, person where profit.id = have_d.id and have_d.nom = person.nom group by source)

Ответ

Проблема известная. :-) Здесь найдете решение.

Где может использоваться .* и ->*?

То есть .* - доступ к указателю на член класса и ->* - доступ к указателю на член класса по указателю. Покажите на примерах.

Ответ

Вот далеко не полный список примеров:
с сайта МС большая статья на codeproject аналогичный вопрос на SO ещё один
да, все это на английском, но там есть примеры на с++, а он как известно и в Африке с++.

Передача параметров в класс

Необходимо создать класс. Он будет унаследован от одного из стандартных классов достаточно популярной библиотеки (не важно - предком может быть QObject Qt или CObject из MFC). При этом возникает проблема, что в класс нужно передать определенное количество параметров. Их можно передать тремя способами: в конструкторе. с помощью некой дополнительной сущности в виде метода init() с нужным количеством параметров. сделать нужное количество сеттеров и внутренних переменных класса, которые будут устанавливаться в процессе работы. У каждого способа есть плюсы и минусы. У конструктора есть серьезный плюс, что объект сразу получается готовый. У него нет промежуточных состояний. С методом init() получается, что его нужно не забыть вызвать с правильными аргументами один раз при создании объекта. Дальнейшие вызовы нежелательны (можно, например, устроить себе утечки памяти). С другой стороны, между вызовом конструктора и ф-цией init() объект получается в каком-то непонятном промежуточном состоянии, когда его полноценное использование невозможно. В третьем случае из-за обилия ф-ций запросто можно запутаться и что-то забыть. При этом у всех внутренних переменных класса, получается, должны быть какие-то значения "по умолчанию", иначе без вызова этих сеттеров экземпляр класс будет неработоспособен. С конструкторами минус мне кажется в том, что если существует достаточно большое кол-во опциональных входных параметров, то получается жесткая путаница в голове у компилятора и он просто не сможет собрать код. В конце-концов можно все параметры попытаться запаковать в структуру и передавать в конструктор указатель на нее. Но как-то это не лаконично. Например, MyObject::MyObject(int a, int b, int c); // GOOD. никаких параметров по умолчанию MyObject::MyObject(int a = 1, int b = 2; int c = 4); // GOOD MyObject::MyObject(QObject *parent = 0, int b = 2, int c = 4); //а оно вообще соберется? и не будет ли конфликта с предыдущим вариантом?
typedef struct {int *first; QObject **parent; int *b; int *c;} arguments; QObject *parent = 0; int b = 2; int c = 4; arguments ar = {NULL, &parent, &b, &c}; // NULL - как бы аргумента "нет" MyObject::MyObject(arguments &data); // нифига неизящно Короче, прошу совета - как лучше делать. Понятно, что универсальных случаев нет, но какие-то рекомендации должны существовать.

Ответ

По поводу трех способов. 2 (с методом init) - это грустно. Инициализация должна быть внутри конструктора. Хотя, некоторые "метры", изобретая Tizen (новую ОС для телефонов), выдают перлы. Доставляет и вызов метода RemoveAll в конце - как бы uninit:) третий способ это размазанный init. По факту (если set'еры имеют хоть какую то логику), приведет к трудностям инициализации - объект может находиться в состоянии кота одного известного ученого(комикс в тему). С конструкторами минус мне кажется в том, что если существует достаточно большое кол-во опциональных входных параметров, то получается жесткая путаница в голове у компилятора и он просто не сможет собрать код. Думаю, у программиста скорее наступит путаница:) а компилятор либо скомпилирует, либо нет. Как бы я делал. У таких сложных классов сделал бы приватные конструкторы (что бы их кто не попади не конструировал). Отдельно сделал бы фабрику, которая по запросу отдавала сконструированный объект (такая себе сборка паттернов фабрика и строитель). Если какой то объект может существовать в десяти разных вариантах, то значит нужно десять разных функций. При этом эти функции могут иметь один-два параметра, так и принимать другой класс/структру в качестве параметра. Так как имена будут разными, то и компилятор не запутается, и человек. (подсмотреть пример ). Второй вариант - это сделать класс, у которого конструктор будет принимать десятки параметров (но мне смутно вериться, что такой класс реально нужен, об этом ниже). И этот конструктор должен быть protected. На каждый специфический случай заводится отдельный наследник с минимумом параметров в конструкторе. Если в какой то момент кажется, что нужно добавить ещё over9000 параметров, нужно подумать, может нужно 2-3 различных класса наследника? Пример из реальной жизни - в windows много оконных элементов - окна. и представьте, если бы у Вас был только один класс окно, который делал все разновидности - окно, кнопку, поле редактирования. Третий способ. То, что нужно так много параметров, подсказывает, что похоже проектируется "божественный класс". Поэтому и вылазят такие сложности. Может с этого класса можно выделить часть данных+кода в отдельный класс/классы? А там и архитектура упростится.

Вопрос про указатели

Здравствуйте!
Есть в C++ указатели, это область памяти которая содержит адрес, по которому в свою очередь расположены данные. И меня интересуют следующие вопросы:
Когда мы выделяем память оператором new компилятор создает некую переменную и переводит указатель на нее? Не совсем понятно, как это выглядит в памяти. Если у нас есть структура (объект структуры), мы создаем указатель на объект типа этой структуры, как это всё выглядит в памяти? Создается один указатель (какой у него будет размер?) или какие-то хитрые манипуляции с указателями на указатели (структура же может иметь свои поля и методы и может на них, не видимо для программиста, что-то хитрое провернуто)?

Ответ

1) компилятор вставляет специальный код, который вызывает функцию выделения памяти (malloc к примеру, хотя никто не мешает выделить вначале много памяти, а потом выдавать кусочками). Эта функция возвращает указатель. Его значение присваивается переменной. При необходимости проводит инициализацию (то есть mov).
Пример (сильно синтетический! память не освобождается! ничего не инициализируется! только для примера!)
int f(int x) { int * c = new int[10]; return c[0]; }
получаем такой где то код (для gcc)
f(int): sub rsp, 8 mov edi, 40 # это размер 10 * sizeof(int) call operator new[](unsigned long) # собственно выделение памяти mov eax, DWORD PTR [rax] add rsp, 8 ret
то есть, программа сама себе выделяет 40 байт памяти. Да, именно сама себе. Компилятор только вставляет вызов специальных функций (которые иногда называют встроенными (builtin) или "магическими" (magick)).
Конечно, никто не мешает компилятору самостоятельно зарезервировать память в бинарнике, а вместо выделения просто прописывать указатель на эту часть памяти. В моем синтетическом примере компилятор мог в принципе и 4 байта выделить.
2) в случае структуры компилятор рассчитывает, сколько места нужно под структуру. Обычно оно не меньше, чем выдает sizeof(имя_структуры). Эта память выделяется одним куском. Всем полям присваиваются смещения.
struct data { int a; int b; int * d; };
void f(int x) { data * c = new data; c->a = 1; c->b = 2; c->d = 0; }
получаем код
f(int): mov edi, 16 # это размер структуры push rax call operator new(unsigned long) # выделяем память mov DWORD PTR [rax], 1 # это поле a. оно находиться по нулевому адресу mov DWORD PTR [rax+4], 2 # это поле b mov QWORD PTR [rax+8], 0 # а указатель занимает 8 байт, поэтому размер структуры 16. pop rdx ret
До этого момента от классического C ничего не отличается. Но в С++ структуры могут иметь конструктор. В этом случае компилятор вставит его вызов.
В том случае, если структура содержит внутри себя другие структуры, то создается комбинация. И снова пример:
struct temp { int c; int d;
};
struct data { int a; int b; temp f; };
void f(int x) { data * c = new data; c->a = 7; c->b = 2; c->f.d =5; }
и его код
f(int): push rax mov edi, 16 call operator new(unsigned long) mov DWORD PTR [rax], 7 mov DWORD PTR [rax+4], 2 mov DWORD PTR [rax+12], 5 pop rdx ret
Я специально выбрал различные значения, что бы можно было найти соответствия. Как видно, компилятор просто вставил структуру и на уровне кода теперь формально есть только одна "структура":
struct fake { int a; int b; int c; int d; };
Остался только вопрос с функциями, которые могут иметь структуры. Здесь все просто. Обычно компилятор добавляет неявный параметр к таким функциям, в котором передает указатель на структуру. Саму структуру никак модифицировать не нужно - для них ведь нет полиморфизма - в любом случае тип структуры будет известный и можно вставить правильный вызов.

Дерево в SQL

Всем добрый день. У меня появился такой вопрос. Скажем имеется таблица в которой хранится древовидная структура. Допустим в таблице есть Id - ид записи и IdParent - ид родителя. Как можно с помощью sql запроса выбрать самого верхнего родителя у записи с id = 10? Возможно ли вообще такое средствами sql?

Ответ

Возможность создания рекурсивных запросов есть начиная с SQL 1999. Это возможно с помощью оператора WITH. В MS Sql будет выглядеть так: WITH rec AS ( SELECT * FROM MyTable WHERE Id = 10
UNION ALL
SELECT mt.* FROM MyTable mt JOIN rec p ON mt.parentID = p.id ) SELECT ParentId FROM rec where Id = 10 Если не ошибаюсь, в MySql это работать не будет. Насчет Oracle - не в курсе