»нформатика


ќлимпиадные задачи по информатике - часть 11


 


†(y2

Ц y1 )×( x Ц x1) - (x2 Ц x1)×(y Ц у1) = 0;

†(у4

Ц у3)×(x Ц x3) - (x4 Ц x3)×(у Ц y3) = 0.

 

–ешение этих уравнений может быть проведено вычислением определителей D, Dx, Dy приведенной системы уравнений:

 

†(у2

Ц у1)×х - (х2 Ц х1)×у = (у2 Ц y1)×х1 - (x2

Ц x1)×y1;

†(у4

Ц y3)×х - (х4 Ц х3) ×у = (у4 Ц у3)×х3- (x4 Ц x3)×y3,

 

дл€ которой будет справедлив следующий набор расчетных формул:

 

х = Dx/D;

у = Dy/D;

D = (у2 - у1)×(х4 - x3) - (x2 - x1)×(y4

- †y3);

†Dx = [(y2 - yl)×xl - (х2 Ц x1)×y1] - (x4

Ц х3) - (x2 Ц x1)×[(y4 Ц y3)×x3 - (х4

Ц х3)×y3];

Dy = (у2 - у1)×[(у4

Ц у3)×х3

- (x4 - x3)×у3] - [(у2 Ц y1)×x1 - (х2

Ц x1)×y1]×(y4 Ц y3).

 

‘акт пересечени€ пар отрезков может быть установлен из этих же уравнений подстановкой в правые части координат точек альтерна­тивного отрезка и сравнением значений этих выражений. ј именно отрезок [(х3, у3) - (х4, у4)] пересекает линию, проход€щую через отрезок [(x1, y1) - (х2, у2)], если эти выражени€ имеют разные знаки:

 

(у2

- у1)×(х3 Ц x1) - (х2 Ц х1)×(y3 Ц у1) ´ (у2 - у1)×(х4

Ц x1) - (х2 Ц x1)×(y4 Ц y1) £

0.

 

—оответственно, отрезок [(х1, у1) - (х2, у2)] пересекает линию, проход€щую через отрезок [(х3, у3) - (х4, у4)], если аналогичные выражени€ имеют разные знаки:

 

(у4

Ц у3)×(х1

Ц х3) - (х4 Ц х3)×(у1 Ц у3)´(у4

Ц у3)×(х2

Ц х3) - (х4 Ц х3)×(у2 Ц у3) £ 0.

 

» наконец, самый тонкий момент - это частные случаи, когда отрезки ломаной оказываютс€ на одной пр€мой линии. ¬ этом случае отрезки либо вообще не пересекаютс€, либо имеют общую часть, которую можно определить из взаимного расположени€ отрезков на пр€мой.

¬ последнем случае обща€ часть отрезков находитс€ из взаимо­расположени€ отрезков [(х1, у1) - (х2, у2)] и [(х3, у3) - (х4, у4)] на пр€мой.


Ќачало  Ќазад  ¬перед