10902. Подбор палочек

Стен имеет n палочек разной длины. Он бросает их на пол одну за одной. Помогите Стену найти все палочки, которые лежат сверху (которые не перекрывает сверху ни одна другая палочка). Стен заметил, что последняя брошенная палочка всегда будет верхней. Палочки тонкие и их толщиной можно пренебречь.

Вход. Первая строка каждого теста содержит количество палочек n (1 £ n £ 100000). Следующие n строк задают координаты коцов палочек в том порядке, в котором их бросал Стен на пол. Последний тест содержит n = 0 и не обрабатывается.

Выход. Для каждого теста вывести список палочек, которые находятся сверху. Список верхних палочек выводить в том порядке, в котором они бросались на пол.

Пример входа

5
1 1 4 2
2 3 3 1
1 -2.0 8 4
1 4 8 2
3 3 6 -2.0
3
0 0 1 1
1 0 2 1
2 0 3 1
0

Пример выхода

Top sticks: 2, 4, 5.
Top sticks: 1, 2, 3.

РЕШЕНИЕ

геометрия + перебор

Анализ алгоритма

Для решения задачи достаточно реализовать переборный алгоритм. Для каждой пары номеров отрезков i и j (i < j, отрезок i в списке идет раньше j) следует проверить, пересекаются ли они. Если отрезки пересекаются (отрезок j накладывается на i), то удалить отрезок i из рассмотрения. После выполнения описанной процедуры за время O(n²) останутся лишь верхние отрезки, которые и следует вывести.

Реализация алгоритма

Координаты начала и конца каждого отрезка храним в векторе v. Вектор list хранит множество входных отрезков.

vector<double> v(4,0);

vector<pair<vector<double>,int> > list;

vector<pair<vector<double>,int> >::iterator iter;

В дальнейших вычислениях будут использоваться функции нахождения минимума min и максимума max двух чисел.

double min(double i, double j)

{

return (i > j) ? j : i;

}

double max(double i, double j)

{

return (i > j) ? i : j;

}

Пусть концы отрезков AB и CD имеют координаты: A(x₁,y₁), B(x₂,y₂), C(x₃,y₃), D(x₄,y₄). Функция RectanglesIntersects принимает в качестве аргументов 8 координат концов отрезков и выводит 1, если прямоугольники, ограничивающие отрезки AB и CD, пересекаются. Иначе функция возвращает 0.

int RectanglesIntersects(double x1,double y1,double x2,double y2,

double x3,double y3,double x4,double y4)

{

if ((x3 - x2) * (x4 - x1) > 0) return 0;

if ((y3 - y2) * (y4 - y1) > 0) return 0;

return 1;

}

Функция intersect проверяет, пересекаются ли отрезки AB и CD. Сначала проверяется пересечение ограничивающих прямоугольников. Если они пересекаются, то строятся вектора AC, AB, AD, CA, CB, CD (например, координаты вектора CD содержатся в переменных CDx и CDy) и вычисляются векторные произведения, указанные в пунктах 2 и 3. В зависимости от значений векторных произведений формируется возвращаемое значение. Оно равно 1, если отрезки AB и CD пересекаются и 0 иначе.

double intersect(double x1,double y1, double x2, double y2,

double x3,double y3, double x4, double y4)

{

double ABx, ABy, ACx, ACy, ADx, ADy;

double CAx, CAy, CBx, CBy, CDx, CDy;

double ACxAB, ADxAB, CAxCD, CBxCD;

if (!RectanglesIntersects(min(x1,x2),min(y1,y2),max(x1,x2),max(y1,y2),

min(x3,x4),min(y3,y4),max(x3,x4),max(y3,y4))) return 0;

ACx = x3 - x1; ACy = y3 - y1;

ABx = x2 - x1; ABy = y2 - y1;

ADx = x4 - x1; ADy = y4 - y1;

CAx = x1 - x3; CAy = y1 - y3;

CBx = x2 - x3; CBy = y2 - y3;

CDx = x4 - x3; CDy = y4 - y3;

ACxAB = ACx * ABy - ACy * ABx;

ADxAB = ADx * ABy - ADy * ABx;

CAxCD = CAx * CDy - CAy * CDx;

CBxCD = CBx * CDy - CBy * CDx;

return ACxAB * ADxAB <= 0 && CAxCD * CBxCD <= 0;

}

Основной цикл программы. Читаем количество палочек n, очищаем вектор отрезков list. Вводим координаты очередного i - го отрезка в массив v. Просматриваем отрезки, хранящиеся в массиве list и удаляем те, которые пересекаются с i - ым. Заносим i - ый отрезок в массив list.

while(scanf("%d",&n),n)

{

list.clear();

for(i = 1; i <= n; i++)

{

scanf("%lf %lf %lf %lf",&v[0],&v[1],&v[2],&v[3]);

for(iter=list.begin();iter<list.end();)

if (intersect((*iter).first[0],(*iter).first[1],(*iter).first[2],

(*iter).first[3],v[0],v[1],v[2],v[3])) list.erase(iter);

else iter++;

list.push_back(make_pair(v,i));

}

Выводим список номеров отрезков, находящихся сверху. Номера отрезков разделяем запятыми, в конце списка выводим точку.

printf("Top sticks: ");iter=list.begin();printf("%d",(*iter++).second);

while(iter<list.end()) printf(", %d",(*iter++).second);

printf(".\n");

}