 Задача: Найти все параллелограммы, которые могут быть построены с тремя вершинами во множестве точек А и одной вершиной в точке C Пусть нам задано множество точек A и точка C. Необходимо найти все параллелограммы, одна из вершин которых - C, а остальные 3 содержатся во множестве A. Для того, чтобы можно было быстрее находить первое вхождение вектора в массиве, а также убирать повторные вхождения в какой-то массив, мы упорядочим векторы и тройки следующим образом: Для решения этой задачи с количеством операций, пропорциональным N2 log2 N , где N - количество вершин, будем использовать следующий алгоритм: 1) заполним массив vect, который будет содержать все вектора, которые можно провести между двумя различными точками множества A // перебираем каждую упорядоченную пару различных точек из A for(i=0;i<point_cnt;i++) { for(j=0;j<point_cnt;j++) { if(i==j) continue; // добавляем вектор из Aj в Ai {t.l,t.m} в массив vect и запоминаем из какой вершины в какую этот // вектор идёт t.l=a[j].l-a[i].l; t.m=a[j].m-a[i].m; t.b=i; t.e=j; vect[vect_cnt]=t; vect_cnt++; } } 2) сортируем полученный массив векторов 3) для каждой вершины из множества A проделаем следующую операцию: Ищем вектор c->Ai (в массиве vect одинаковые элементы идут подряд, поэтому найдём первое вхождение двоичным поиском, а дальше будем обрабатывать их подряд). Дальше мы будем перебирать все вектора, начиная с текущего, пока не встретим вектора, не равного искомому, или массив не закончится. В результат будем добавлять все тройки, в которых все 3 числа различные, а если построить параллелограмм на этих вершинах, он не будет вырожден. Первое вхождение вектора находится следующей функцией (количество операций порядка log(N2) ): int binary_search(vector t) { //l - левая граница интервала поиска, r - правая граница интервала поиска //с - середина [l;r] (если l+r не делится на 2, то округляем вниз) int l=0,r=vect_cnt-1,c; while(l<r) { c=(l+r)/2; if(vector_islesser(&vect[c],&t)) { // если текущий элемент меньше t, то левее будут элементы ещё меньшие, // а значит искать будем справа от текущего положения l=c+1; } else { // если текущий элемент больше или равен t, то значит нужно искать элемент // левее текущего положения или в этом положении r=c; } } return l; } Т.к. точки не повторяются, то, выбрав первую и вторую точки, мы можем N-1 способами выбрать третью, а четвёртая точка может быть выбрана единственным образом: от третей точки отложить вектор "вторая точка->первая точка" (точки нумеруются в порядке обхода вершин параллелограмма). Значит выбрав одну точку, дополнить её остальными точками из A до параллелограмма можно не более чем N способами. Поэтому внутренний цикл будет работать не более N раз cur_cnt=0; for(i=0;i<point_cnt;i++) { // составляем вектор t, который будем искать t.l=a[i].l-c.l; t.m=a[i].m-c.m; t.b=-1; t.e=-1; tr.a1=i; //находим первое вхождение этого вектора в массив p=binary_search(t); while(p<vect_cnt&&vector_isequal(vect[p],t)) { //идём по массив vect, начиная с p и добавляем каждую "хорошую точку" в результирующий массив tr.a2=vect[p].e; tr.a3=vect[p].b; tr=order(tr); if(triple_isgood(tr)) { cur_triple[cur_cnt]=tr; cur_cnt++; } p++; } } 4) уберём повторяющиеся точки из cur_triple и переносим их в массив parallel // упорядочиваем массив cur_triple, в котором могут быть повторяющиеся тройки triple_quicksort(cur_cnt-1,cur_triple); if(cur_cnt!=0) { //уберём повторения, перенеся в массив parallel по следующему принципу: //1) перенесём первую тройку в ответ //2) будем перебирать элементы массива и добавлять в ответ каждую //тройку, которая отличается от предыдущей cnt=1; parallel[0]=cur_triple[0]; for(i=1;i<cur_cnt;i++) { if(!triple_isequal(cur_triple[i-1],cur_triple[i])) { parallel[cnt++]=cur_triple[i]; } } parallel_cnt=cnt; } В результате работы этого алгоритма массив parallel будет содержать тройки с номерами вершин, которые образуют параллелограммы.
|
|||||||
 |
Основы программирования |
|
|
|