Будем просматривать массив слева направо, то есть по возрастанию координат концов отрезков котангенсов. Чтобы отследить, находится ли текущая точка в секторе нахождения какой-либо овцы, будем поддерживать счетчик числа овец, поражаемых при текущем направлении выстрела. Сначала этот счетчик инициализируется нулем. Рассмотрим следующие случаи:

1. Элемент массива соответствует началу отрезка котангенсов для овцы. Если счетчик числа овец равен нулю, то запомним в переменной L индекс этого элемента. Пусть R – точка отрезка котангенсов для этого элемента. Увеличим на 1 счетчик числа овец.

2. Элемент массива соответствует концу отрезка котангенсов овцы. Уменьшим на 1 счетчик числа овец.

3. Элемент массива соответствует началу отрезка котангенсов для волка. Ничего не делаем. Чем больше волков в направлении выстрела, тем лучше.

4. Элемент массива соответствует концу отрезка котангенсов для волка.

1. Счетчик числа овец равен нулю. Чтобы волк не остался цел, необходим выстрел в направлении, соответствующем найденному концу отрезка. При этом будут убиты все волки, находящиеся на этом направлении. Нужно просмотреть массив назад, найти начала отрезков для волков и убрать из массива (пометить специальным признаком) концы этих отрезков. Для упрощения этой процедуры можно использовать счетчик числа волков в текущем направлении выстрела. К счетчику числа выстрелов прибавим 1.

2. Счетчик числа овец больше нуля. Чтобы текущий волк был убит, необходимо произвести выстрел в том направлении, при котором волк поражается, но ни одна овца не затрагивается. В качестве такого значения по отрезкам котангенсов можно взять R-ε. Обработаем такой выстрел аналогично предыдущему случаю. Если же начало отрезка для данного волка не меньше R, то решение невозможно, т.к. этот волк не может быть убит без поражения овец.

Таким образом просмотрим весь массив. Если не возникнет ситуаций, когда какой-либо волк не может быть убит, то счетчик числа выстрелов даст необходимый ответ.

Приведем текст программы по этой задаче. Заметим, что при большей размерности исходных данных (N, M до10⁵) придется использовать вместо Турбо Паскаля какую-либо другую среду программирования (например Delphi) и применять один из методов быстрой сортировки [11].

Program Wolves;

Const Max=4000; { (M+N)*2 }

Label Konec;

Type

Point=record {концы отрезков котангенсов для волков и овец}

X: real; {координата в пределах [-1000; 1000]}

Vid: char; {'[' для левого конца и ']' для правого}

Pr: char; {'w'-волк, 's'-овца}

Ind: integer; {индекс в массиве парной скобки}

Flag: boolean; {False-исключение точки из рассмотрения}

End;

Var

N,M,L,K,i,j,ii,jj: integer;

WS: array [1..Max] of Point;

KolS: integer; {счетчик количества выстрелов}

Sheep: integer;

{счетчик количества овец для текущего направления выстрела}

A,B,X1,Y1,X2,Y2: real;

Fin,Fout: text;

Procedure Swap(Var P,Q: point);

{обмен значений элементов массива WS }

Var

S: point;

Begin

S:=P;

P:=Q;

Q:=S;

End;

Function Eq(P,Q: real): boolean; {проверка равенства P и Q}

Begin

if Abs(P-Q)<0.0001 then Eq:=True

else Eq:=False;

End;

Function Prior(P: point): integer;

{ приоритет точек концов отрезков по возрастанию:

начало отрезка для овцы, начало для волка,

конец для волка, конец для овцы }

Begin

if (P.Pr='s') and (P.Vid='[') then Prior:=0;

if (P.Pr='w') and (P.Vid='[') then Prior:=1;

if (P.Pr='w') and (P.Vid=']') then Prior:=2;

if (P.Pr='s') and (P.Vid=']') then Prior:=3;

End;

Procedure Sort; {сортировка массива WS}

Var

b: boolean;

Begin

For i:=2 to K do

For j:=K downto i do { модифицированный пузырек }

begin

b:=False;

if (WS[j].X<WS[j-1].X) then b:=True

else

if Eq(WS[j].X,WS[j-1].X) then

begin

ii:=Prior(WS[j]);

jj:=Prior(WS[j-1]);

{ приоритет в порядке возрастания:

начало отрезка для овцы, начало для волка,

конец для волка, конец для овцы }

if ii<jj then b:=True;

end;

if b then {обмен}

begin

ii:=WS[j-1].Ind;

jj:=WS[j].Ind;

Swap(WS[j-1],WS[j]);

{далее корректировка индексов после обмена}

if WS[j].Ind=j then

{WS[j-1] и WS[j] ссылались друг на друга,

в них были парные скобки}

begin

WS[j-1].Ind:=j;

WS[j].Ind:=j-1;

end

else

begin

WS[jj].Ind:=j-1;

WS[ii].Ind:=j;

WS[j-1].Ind:=jj;

WS[j].Ind:=ii;

end;

end;

end;

End;

Begin

Assign(Fin,'input.txt');

Reset(Fin);

Assign(Fout,'output.txt');

Rewrite(Fout);

ReadLn(Fin,N,M);

KolS:=0; {количество выстрелов}

if N=0 then {волков нет}

begin

Close(Fin);

WriteLn(Fout,KolS);

Goto Konec;

end;

K:=0; {счетчик для массива WS}

For i:=1 to N+M do {ввод для волков и овец}

begin

ReadLn(Fin,X1,Y1,X2,Y2);

K:=K+1;

A:=X1/Y1; {котангенсы}

B:=X2/Y2;

WS[K].X:=A;

WS[K].Flag:=True;

if A<B then WS[K].Vid:='['

else WS[K].Vid:=']';

if ((K+1) div 2) <= N then WS[K].Pr:='w' {волк}

else WS[K].Pr:='s'; {овца}

WS[K].Ind:=K+1;

K:=K+1;

WS[K].X:= B;

WS[K].Flag:=True;

if A<B then WS[K].Vid:=']'

else WS[K].Vid:='[';

if (K div 2) <= N then WS[K].Pr:='w'

else WS[K].Pr:='s';

WS[K].Ind:=K-1;

end;

Close(Fin);

Sort;

{сортировка пузырьком массива WS, для больших M и N

нужна быстрая сортировка}

Sheep:=0; {счетчик числа овец}

For i:=1 to K do

if WS[i].Flag then {точка не исключена}

begin

if (WS[i].Vid='[') and (WS[i].Pr='s') then

{начало отрезка котангенсов для овцы}

begin

if Sheep=0 then L:=i; {индекс начала отрезка овец}

Sheep:=Sheep+1;

end;

if (WS[i].Vid=']') and (WS[i].Pr='s') then

{конец отрезка котангенсов для овцы}

Sheep:=Sheep-1;

if (WS[i].Vid=']') and (WS[i].Pr='w') then

begin

if Sheep=0 then {овец в данном направлении нет}

begin

KolS:=KolS+1; {стреляем}

For j:=i downto 1 do

if (WS[j].Vid='[') and (WS[j].Pr='w') then

begin

ii:=WS[j].Ind; {индекс точки конца отрезка}

WS[ii].Flag:=False; {исключение точки}

end;

end

else {в данном направлении есть овцы}

begin

ii:=WS[i].Ind;

{индекс начала отрезка текущего волка}

if (WS[ii].X>WS[L].X) or

Eq(WS[ii].X,WS[L].X) then

{текущий волк перекрыт отрезком овец}

begin

WriteLn(Fout,'No solution');

Goto Konec;

end;

KolS:=KolS+1; {стреляем}

For j:=L downto 1 do

if (WS[j].Vid='[') and (WS[j].Pr='w') then

begin

ii:=WS[j].Ind; {индекс точки конца отрезка}

WS[ii].Flag:=False; {исключение точки}

end;

end;

end;

end;

WriteLn(Fout,KolS);

Konec:

Close(Fout);

End.

Задачи для самостоятельного решения

7.1. Отрезки (6)

На числовой прямой задано N отрезков, пронумерованных в порядке их ввода, начиная с 1. Отрезки могут пересекаться. Отрезок называется простым, если в нем не содержится целиком никакой другой. Найдите все простые отрезки из заданного набора.

Ввод из файла INPUT.TXT. В первой строке записано число N (1 ≤ N ≤ 510⁵). В следующих N строках заданы целочисленные координаты левого и правого концов отрезка a_i, b_i (-10000 ≤ a_i, b_i ≤ 10000).

Вывод. В первую строка файла OUTPUT.TXT вывести количество простых отрезков. Во вторую – в порядке возрастания последовательность номеров простых отрезков. Если простых отрезков нет, в единственной строке вывести 0.

Ограничения: время 1 с.

Примеры

Ввод 1 Ввод 2

3 3

1 10 5 10

3 3 5 10

10 20 8 100

Вывод 1 Вывод 2

2 1

2 3 3

7.2. Ремонт дорог (3)

После схода с рельсов нескольких поездов, следовавших из пункта A в пункт B, решено отремонтировать железную дорогу. Множество независимых экспертов представили описание участков дороги, нуждающихся в ремонте, в виде отрезков, которые могут пересекаться и лежать один внутри другого. Ремонту подлежат только эти участки. Ремонтная бригада в состоянии отремонтировать любой участок дороги, заданный отрезком. Найти минимальное количество бригад для ремонта. Напоминаем, что концы отрезка считаются принадлежащими ему.

Ввод из файла INPUT.TXT. Первая строка содержит количество отрезков для ремонта N (1  N  1000). В следующих N строках задаются сами отрезки в виде двух целых чисел X и Y через пробел (0  X,Y  10000).

Вывод в файл OUTPUT.TXT в виде единственного целого числа.

Пример

Ввод

3

2 5

8 10

4 6

Вывод

2

7.3. Прямоугольники (6)

На координатной плоскости задано N прямоугольников со сторонами, параллельными координатным осям. Найти площадь фигуры, получающейся в результате объединения прямоугольников.

Ввод из файла INPUT.TXT. В первой строке содержится значение N (1 ≤ N ≤ 300). В каждой из следующих N строк – четыре целых числа A_i, B_i, C_i, D_i через пробел, определяющие координаты левого верхнего и правого нижнего углов очередного прямоугольника (-1000 ≤ A_i, B_i, C_i, D_i ≤ 1000).

Вывод в файл OUTPUT.TXT единственного целого числа – площади фигуры.

Пример

Ввод

2

5 15 25 5

0 10 20 0

Вывод

325

7.4. Муравьи (6)

Юный натуралист Билл изучает муравьев. Его муравьи питаются исключительно яблоками, растущими на диких яблонях. Имеется карта с координатами N муравейников и N яблонь. Муравьи из каждого муравейника добираются до яблони кратчайшим путем по прямой. Требуется так распределить яблони между муравейниками, чтобы

• у каждого муравейника была единственная яблоня;

• каждая яблоня принадлежала только одному муравейнику;

• пути муравьев из разных муравейников к своим яблоням не пересекались.

Ввод из файла INPUT.TXT. Первая строка единственное целое число N (1 ≤ N ≤ 100). Далее в N строках заданы через пробел координаты X_i, Y_i (-10000 ≤ X_i, Y_i ≤ 10000) муравейников. В последующих N строках заданы координаты яблонь. Никакие три точки не лежат на одной прямой.

Вывод в файл OUTPUT.TXT состоит из N строк по одному целому числу в строке. Число в i-й строке определяет номер яблони, предназначенной для i-го муравейника.

Пример

Ввод

5

-42 58

44 86

7 28

99 34

-13 -59

-47 -44

86 74

68 -75

-68 60

99 -60

Вывод

4

2

1

5

3

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