Задача о разрезании прямоугольника

[Ильнар70]

Помогите решить задачу на паскале.
В первой строке входного файла записана ширина w и высота h торта (1<=w,h<=20). Во второй строке записано количество разрезов n (0<=n<=50). В остальных n строках записаны четверки целых чисел x1,y1,x2,y2 - координаты двух противоположных углов разреза (0<=x1,x2<=w, 0<=y1,y2<=h).
Нужно записать количество получившихся кусков, на которые распадается этот прямоугольник после того, как произвели n разрезов.
Даже не представляю себе, как решать задачи такого типа. Может, надо чертить прямоугольник, а потом линии разреза? Потом как-то пересчитать получившиеся куски?

[LeBron]

Самое примитивное решение - это прогнать Монте-Карло))) И оно может даже пройти при плохих тестах. Т.е. Взять, допустим, миллион точек на торте, и для каждой проверить, как она размещена относительно все прямых (слева или справа, если их векторизировать). Каждый уникальный набор размещений - новый кусок.
Вариант получше - найти все точки пересечения прямых на торте, отсортировать их по одной из координат, и дальше что-то типа выметающей прямой использовать. Там будет только одна проблемка, если есть прямая, параллельная координатной оси... Но это можно поправить.

А вообще есть хорошее алгоритмическое решение, основанное только на уравнениях прямых, но я его никогда не читал (мне хватало выметающей прямой), а сейчас не могу найти.

[Ильнар70]

Вот бы мне это уравнение. Просто я к олимпиаде готовлюсь, а такие типы задач часто встречаются)
Пожалуйста, опишите по-подробней, как решать такие задачи с помощью выметающей прямой.

[WhiteSpirit]

Как мне кажется...
После первого разреза торт разделяется на 2 куска.
Делаем второй разрез, если он пересекается с первым, то будет 4 куска, если нет, то 3. Ну и так далее. То есть, количество кусков = количество разрезов + 1 + количество пересечений, при этом пересечения считаются в пределах прямоугольника, но не на периметре.
Осталось только посчитать, сколько пересечений имеет каждая линия разреза.