Задача 9.
На прямой окрасили N отрезков.Известны координата L[I] левого конца отрезка и координата R[I] правого конца I-го отрезка для I=1, ..., N. Найти сумму длин всех окрашенных частей прямой.
Примечание. Число N столь велико, что на выполнение N*N даже простейших операций не хватит времени.
МОДИФИКАЦИЯ. На окружности окрасили N дуг. Известны угловая координата L[I] начала и R[I] конца I-ой дуги (от начала к концу двигались, закрашивая дугу, против часовой стрелки). Какая доля окружности окрашена?
|
Решение задачи 9.
Будем моделировать закрашивание этих N отрезков.
Достаточно отсортировать отрезки в порядке неубывания координат левых концов. После этого осуществляется простой просмотр упорядоченных отрезков с анализом следующих возможных ситуаций:
1. Если текущий отрезок пересекается с закрашиваемым отрезком (его левая координата не больше правого конца закрашиваемого отрезка), то новым правым концом закрашиваемого сейчас отрезка становится более правый из концов закрашиваемого и текущего отрезков.
2. Если текущий отрезок не пересекается с закрашиваемым отрезком, то закраска предыдущего отрезка закончена, его длина суммируется с длиной уже закрашенной части, а закрашиваемым отрезком становится текущий отрезок.
Процесс продолжается до тех пор, пока не будут просмотрены все отрезки. После этого длина последнего закрашенного отрезка суммируется с длиной ранее закрашенной части.
|
