3. Уравнение прямой 2

Зная координаты точки на прямой и координаты вектора , перпендикулярного этой прямой найти уравнение прямой.

Входные данные:

Четыре числа — координаты точки на прямой и координаты вектора нормали к этой прямой.

Выходные данные:

Три числа — коэффициенты А, В и С общего уравнения этой прямой.

Пример

Input.txt	Output.txt
1 2 3 1	3 1-5

Program uravnenie;

Var X0, Y0, A, B: Longint;

Begin

assign(input, 'input');reset(input);

assign(output, 'output.txt'); rewrite(output);

Read(X0, Y0, A, B);

Write(A, ' ', B, ' ', -(A*X0 + B*Y0));

Close(Input); Close(Output);

End.

4. Уравнение прямой проходящей через точку м(х0у0)

перпендикулярной прямой ax+by+c=0.

M(x0,y0)

n1(a1,b1)

n(a,b)

N

Пусть уравнение данной прямой a*x+b*y+c=0

Найдем координаты вектора n1. Так как n1 перпендикулярен n, то их скалярное произведение равно нулю т,е a*a1+b*b1=0. Подберем решения этого уравнения a1:=-b, b1=a. Действительно a*(-b)+b*a=0 истинно.

Тогда уравнение прямой MN имеет вид –b*x+a*y+c₁=0. Для нахождения c₁ используем тот факт, что точка M принадлежит прямой MN. Тогда ее координаты обращают уравнение прямой в истинное числовое равенство.

–b*x₀+a*y₀+c₁=0. Отсюда c₁:=b*x₀-a*y₀ тогда искомое уравнение

-b*x+a*y+b*x₀-a*y₀=0

5. Уравнение прямой проходящей через точку M(x0,y0) параллельно вектору t(m,n).

N Возьмем любую точку N(x,y) на прямой

M Так как векторы MN и t коллинеарны

то их координаты пропорциональны

(x-x0)/m=(y-y0)/n. Или (x-x0)*n=(y-y0)*m

t n*x –m*y+m*y0-n*x0=0. А это есть общее уравнение

прямой, где a=n, b=-m, c=m*y0-n*x0.

Параметрическое уравнение прямой.

В(x2,y2)

C(x,y)

А(x1,y1)

Пусть точка С любая точка прямой АВ. Так как векторы АВ и АС коллинеарны и тогда АС=t*AB

x-x₁=t*(x₂-x₁) отсюда x=x1+ t*(x₂-x₁)

y-y₁=t*(y₂-y₁) y=y1+ t*(y₂-y₁)

где t- любое действительное число.

Угол между двумя прямыми.

Опр. За угол между двумя прямыми принимается наименьший из углов, образованных этими прямыми.

Если прямые параллельны или совпадают, то величина угла между ними равна нулю. Если прямые перпендикулярны, то величина угла между ними 90 градусов.

Пусть a1*x+b1*y+c1=0 и a2*x+b2*y+c2=0 общие уравнения данных прямых, тогда координаты перпендикулярных им векторов n₁ и n₂ равны (a₁,b₁) и (a₂,b₂).

И cos d= (n₁*n₂)/((abs(n₁)*abs(n₂)); Cos d может быть положительным и отрицательным и, в зависимости от этого угол острым или тупым. Так как нам нужен острый угол то берем правую часть по модулю и находим величину угла d=arсcos(abs((n₁*n₂)/((abs(n₁)*abs(n₂)))).

Полярная система координат

Основными понятиями этой системы являются точка отсчета – полюс – и луч, начинающийся в этой точке, – полярная ось.

В полярной системе координат каждой точке на плоскости соответствует пара чисел (с; ц). Координата с – расстояние от точки до полюса, координата ц – угол между полярной осью и отрезком, соединяющим полюс и рассматриваемую точку, который берется со знаком «+», если угол от оси до отрезка вычисляется против часовой стрелки, и со знаком «–» в противоположном случае.

Для полюса с = 0, а угол ц не определен.

Полярные координаты легко преобразовать в декартовы. Пусть (x; y) – координаты точки в декартовой системе координат, (с; ц) – в полярной. Тогда очевидно, что

Формулы обратного перехода:

Рассмотрим несколько элементарных задач.

Все числа во входном файле Input.txt целые, по модулю не превышающие 10000. Величины углов выводить в радианах.

Все вещественные числа выводить с точностью до пятого знака после десятичной точки.

Опр. Полярным углом точки называется угол между направлением на точку и направлением полярной оси.

Задача 7 Полярный угол точки

Даны декартовы координаты точки. Найти величину ее полярного угла.

Входные данные:

Два числа — координаты точки.

Выходные данные:

Одно вещественное число с точностью до пятого знака после десятичной точки- величина её полярного угла.

Пример

Input.txt	Output.txt
2 3	0.98279

Const E = 1e-7;

Var

X, Y: Longint;

A: Extended;

Begin

Assign(Input, 'Input.txt'); Reset(Input);

Assign(Output, 'Output.txt'); Rewrite(Output);

Read(X, Y);

If Abs(X) > E

Then

begin

If (X < 0)and(Y>=0)

Then Write(Pi+ArcTan(Y / X):0:5);

If (X < 0)and(Y<0)

Then Write(ArcTan(Y / X)-pi:0:5);

If ((X > 0)and(Y <=0))or((X>0)and(Y>=0))

Then Write(ArcTan(Y / X):0:5);

end

else

if Y>0 then Write(Pi / 2:0:5)

else Write(-Pi / 2:0:5);

Close(Output);

End.

Задача 8 Угол между векторами

Даны два вектора . Найти угол между векторами.

Входные данные:

Четыре целых числа — координаты двух векторов.

Выходные данные:

Одно число — величина угла между ними с точностью до пятого знака после запятой.

Пример

Input.txt	Output.txt
2 1 3 5	0.56673

Program ugol;

Const E =0.5e-6;

Var X1, Y1, X2, Y2: Longint;

S, V: Extended;

Function VectMul(X1, Y1, X2, Y2: Longint): Longint;

Begin

VectMul := X1 * Y2 - X2 * Y1;

End;

Function ScalMul(X1, Y1, X2, Y2: Longint): Longint;

Begin

ScalMul := X1 * X2 + Y1 * Y2;

End;

Begin

assign(input, 'input.txt); reset(input);

assign(output, 'output.txt'); rewrite(output);

Read(X1, Y1, X2, Y2);

S := ScalMul(X1, Y1, X2, Y2);

V := Abs(VectMul(X1, Y1, X2, Y2));

If Abs(S) < E Then

Write(Pi / 2:0:5)

Else

If S < 0 Then

Write(ArcTan(V / S) + Pi:0:5)

Else

Write(ArcTan(V / S):0:5);

Close(Input);

Close(Output);

End.

Задача 9 Площадь треугольника

Даны координаты вершин треугольника. Вычислить его площадь.

Входные данные:

Шесть целых чисел — координаты трёх вершин треугольника.

Выходные данные:

Одно вещественное число с точностью до трех знаков после десятичной точки— величина площади треугольника.

Пример

Input.txt	Output.txt
0 0 0 2 6 0	6.000

Для вычисления площади треугольника в школьном курсе геометрии используются пять формул. Вот они:

S=0.5*a*h

S=0.5*a*b*sin()

S=sqrt(p*(p-a)*(p-b)*(p-c)) , где p=(a+b+c)/2.

S=p*r, где r – радиус окружности вписанной в треугольник,

p - полупериметр.

S=(a*b*c)/(4*R), где R – радиус окружности описанной вокруг

треугольника

Мы будем использовать формулу площади ориентированного треугольника.

Program square;

Var X1, Y1, X2, Y2, X3, Y3: Longint;

Function streug(X1, Y1, X2, Y2, X3, Y3: Longint): real;

Begin

Streug:= 0.5*(( x2-x1)*( y3-y1)- ( x3-x1)*( y2-y1));

End;

Begin

assign(input, 'input.txt'); reset(input);

assign(output, 'output.txt'); rewrite(output);

Read(X1, Y1, X2, Y2, X3, Y3);

Write(Abs(streug(X1, Y1, X2, Y2, X3, Y3) :0:3);

Close(Input);

Close(Output);

End.

Задача 10 Параллельная прямая

Найти уравнение прямой, параллельной данной и отстоящей от нее на заданное расстояние

Входные данные:

Четыре целых числа — коэффициенты А, В и С общего уравнения прямой и величина R.

Выходные данные:

Три вещественных числа — коэффициенты А, В и С общего уравнения любой из прямых, параллельных заданной и лежащих от неё на расстоянии R.

Пример

Input.txt	Output.txt
0-111	0-1 2

Program uravnenie;

Var A, B, C, R: Longint;

Begin

assign(input, 'input');reset(input);

assign(output, 'output.txt'); rewrite(output);

Read(A, B, C, R);

Write(A, ' ', B, ' ', C - R * Sqrt(A * A + B * B):0:5);

Close(Input);

Close(Output);

End.

Задача 11 Принадлежность точки отрезку

Определить, принадлежит ли точка A(x,y) отрезку с концевыми точками B(x₁,y₁) и C(x₂,y₂)?

Первый способ

Если существует такое p, 0<=p<=1, что pOB+(1-p)OC=OA,где OB ,OAи OC – векторы, то A лежит на отрезке, иначе - нет.

Равенство расписывается покоординатно так:

px₁+(1-p)x₂=x

py₁+(1-p)y₂=y

Из первого уравнения находим p, подставляем во второе: если получаем равенство и 0<=p<=1, то A на отрезке, иначе - нет.

Второй способ

Если realeq(ВС,ВА+АС), то точка А внутренняя, иначе внешняя по отношению к отрезку, то есть если выполняется равенство . ВС=ВА+АС

В А С

Третий способ

Если площадь треугольника ВАС равна нулю и угол между векторами АВ и АС неположительный, то точка А лежит на отрезке иначе не лежит.

Входные данные:

Шесть целых чисел — координаты точки и координаты концов отрезка.

Выходные данные:

Одна строка "YES", если точка принадлежит отрезку, и "NO" в противном случае.

Пример

Input.txt	Output.txt
3 3 12 5 4	YES

Program otrezok;

Var X, Y, X1, Y1, X2, Y2: Longint;

Function VectMul(X1, Y1, X2, Y2: Longint): Longint;

Begin

VectMul := X1 * Y2 - X2 * Y1;

End;

Function ScalMul(X1, Y1, X2, Y2: Longint): Longint;

Begin

ScalMul := X1 * X2 + Y1 * Y2;

End;

Begin

assign(input, 'input');reset(input);

assign(output, 'output.txt'); rewrite(output);

Read(X, Y, X1, Y1, X2, Y2);

If (VectMul(X1 - X, Y1 - Y, X2 - X, Y2 - Y) = 0) and площадь треугольника

равна нулю

(ScalMul(X2 - X, Y2 - Y, X1 - X, Y1 - Y) <= 0) угол между векторами

равен 180 градусов

Then Write('YES')

Else Write('NO');

Close(Input);

Close(Output);

End.

Задача 12 Принадлежность точки прямой

Даны прямая и точка. Принадлежит ли точка прямой.

Входные данные:

Пять целых чисел — координаты точки и коэффициенты А, В и С нормального уравнения прямой.

Выходные данные:

Одна строка "YES", если точка принадлежит прямой, и "NO" в противном случае.

Пример

Input.txt	Output.txt
3 7-21-1	YES

Program tochka;

Const E = 0.5e-6;

Var X, Y, A, B, C: Longint;

Begin

assign(input, 'input');reset(input);

assign(output, 'output.txt'); rewrite(output);

Read(X, Y, A, B, C);

If Abs(A * X + B * Y + C) < E

Then Write('YES')

Else Write('NO');

Close(Input);

Close(Output);

End. Задача 13 Принадлежность точки лучу

Дана точка и луч. Принадлежит ли точка лучу.

Входные данные:

Шесть целых чисел — координаты точки и координаты начала и конца вектора, задающего луч.

Выходные данные:

Одна строка "YES", если точка принадлежит лучу, определяемому вектором, и "NO" в противном случае.

Пример

Input.txt	Output.txt
16 3 7 5 8	NO

Program luch;

Var X, Y, X1, Y1, X2, Y2: Longint;

Function VectMul(X1, Y1, X2, Y2: Longint): Longint;

Begin

VectMul := X1 * Y2 - X2 * Y1;

End;

Function ScalMul(X1, Y1, X2, Y2: Longint): Longint;

Begin

ScalMul := X1 * X2 + Y1 * Y2;

End;

Begin

assign(input, 'input');reset(input);

assign(output, 'output.txt'); rewrite(output);

Read(X, Y, X1, Y1, X2, Y2);

If (VectMul(X1 - X, Y1 - Y, X2 - X, Y2 - Y) = 0) and если точка лежит на прямой

(ScalMul(X2 - X1, Y2 - Y1, X - X1, Y - Y1) >= 0) скалярное произведение>=0,

Then Write('YES') т.е. cosa>=0, то точка лежит на луче

Else Write('NO'); иначе не лежит

Close(Input);

Close(Output);

End.

Задача 14 Положение двух точек и прямой

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

Входные данные:

Семь чисел — координаты двух точек вне прямой и коэффициенты А, В и С её общего уравнения.

Выходные данные:

Одна строка "YES", если точки лежат по одну сторону прямой, и "NO" в противном случае.

Пример

Input.txt	Output.txt
0 0 2 4 2-1-1	YES

Будем считать, что точки лежащие на прямой принадлежат одновременно обеим полуплоскостям, границей которых является данная прямая.

Найдем координаты двух каких-нибудь точек А и В, лежащих на данной прямой. Возьмем любые два значения переменной x и найдем соответствующие им значения y из уравнения прямой. Далее находим ориентированные площади двух треугольников АВМ и АВN -S1 и S2.

M B

N

A

Если S1*S2>=0, то точки лежат по одну сторону от прямой, если S1*S2<0, то по разные.

Program prjmaj;

Var X1, Y1, X2, Y2, A, B, C: Longint;

Begin

assign(input, 'input');reset(input);

assign(output, 'output.txt'); rewrite(output);

Read(X1, Y1, X2, Y2, A, B, C);

If ((A * X1 + B * Y1 + C) > 0) xor

((A * X2 + B * Y2 + C) > 0)

Then Write('NO')

Else Write('YES');

Close(Input);

Close(Output);

End.

О пр. Расстоянием от точки M до фигуры F называется расстояние от точки M до ближайшей точки фигуры F.

М

Фигура F

Найдем расстояние от точки M(x1,y1) до окружности с центром O(x0,y0) и радиусом R. Искомое расстояние равно длине отрезка MN.

MN=SQRT((x0-x1)*(x0-x1)+(y0-y1)*( y0-y1))-R.

M

N N

O

Задача 15 Расстояние от точки до прямой

Дана прямая и точка вне ее. Найти расстояние от точки до прямой.

Входные данные:

Пять целых чисел — координаты точки и коэффициенты А, В и С общего уравнения прямой.

Выходные данные:

Одно вещественное число с точностью до пяти десятичных знаков — расстояние от точки до прямой.

Пример

Input.txt	Output.txt
1111-1	0.70711

Program rastojnie’

Var X, Y, A, B, C: Longint;

Begin

assign(input, 'input');reset(input);

assign(output, 'output.txt'); rewrite(output);

Read(X, Y, A, B, C);

Write(Abs(A * X + B * Y + C) / Sqrt(A * A + B * B):0:5);

Close(Input);

Close(Output);

End.

Задача 16 Расстояние от точки до луча

Дана точка и луч. Найти расстояние от точки до луча.

Входные данные:

Шесть целых чисел — координаты точки и координаты начала и конца вектора, задающего луч.

Выходные данные:

Одно вещественное число с точностью до пяти десятичных знаков — расстояние от точки до луча, определяемого вектором.

Пример

Input.txt	Output.txt
2 1110 2	1.0

M N

O A

Могут быть два случая.

Program luch;

Var X, Y, X1, Y1, X2, Y2: Longint;

Function VectMul(X1, Y1, X2, Y2: Longint): Longint; векторное произведение векторов

Begin

VectMul := X1 * Y2 - X2 * Y1;

End;

Function ScalMul(X1, Y1, X2, Y2: Longint): Longint; скалярное произведение векторов

Begin

ScalMul := X1 * X2 + Y1 * Y2;

End;

Function Len(X1, Y1, X2, Y2: Longint): Extended; длина отрезка

Begin

Len := Sqrt(Sqr(X1 - X2) + Sqr(Y1 - Y2));

End;

Begin

assign(input, 'input');reset(input);

assign(output, 'output.txt'); rewrite(output);

Read(X, Y, X1, Y1, X2, Y2);

If ScalMul(X2 - X1, Y2 - Y1, X - X1, Y - Y1) >= 0 если вектор проведенный

из начала луча в точку образует с

направлением луча угол >90 градусов,

то искомое расстояние равно

расстоянию от точки до прямой

Then

Write(Abs(VectMul(X1 - X, Y1 - Y, X2 - X, Y2 - Y)) / Len(X1, Y1, X2, Y2):0:5)

Else иначе искомое расстояние

это расстояние между двумя точками - данной точкой и началом луча

Write(Len(X, Y, X1, Y1):0:5);

Close(Input);

Close(Output);

End.

Задача 17 Расстояние от точки до отрезка

Дан отрезок и точка. Найти расстояние между отрезком и точкой.

Входные данные:

Шесть целых чисел — координаты точки и координаты концов отрезка.

Выходные данные:

Одно вещественное число с точностью до пяти десятичных знаков — расстояние от точки до отрезка.

Пример

Input.txt	Output.txt
0 4 2 3 2 5	2.0

Если точка принадлежит отрезку, то искомое расстояние равно нулю. Если точка не принадлежит отрезку, то могут быть два случая.

1 ) C 2) C

A N B N A B

Т.е. основание перпендикуляра, опущенного из точки C на прямую AB может принадлежать отрезку или не принадлежать.

В первом случае искомое расстояние равно CN, во втором CA,которые находятся по формуле длины отрезка. В первом случае длину отрезка CN можно найти по формуле нахождения расстояния от точки до прямойCN=(a*x0+b*y0+c)/SQRT(a*a+b*b).

Как отличить первый случай от второго?

Пусть a,b и c - длины отрезков AB, BC и AC соответственно. Если перпендикуляр CN попадает на отрезок AB, то углы ABC и BAC по величине не превосходят 90 градусов (эти оба угла не тупые).

По теореме косинусов

b² = a² + c² - 2*a*c*cos BAC

и

c² = a² + b² - 2*a*b*cos ABC

Если углы ABC и BAC не тупые, то cos ABC и cos BAС неотрицательны, и слaгаемые -2*a*c*cos BAC и -2*a*b*cos ABC в приведенных выше формулах вычитаются из суммы квадратов, т.е. в случае, когда перпендикуляр попадает на отрезок AB, должны выполняться одновременно два неравенства

b² <= a² + c² и c² <= a² + b²,

Если хотя бы одно неравенство нарушается, то перпендикуляр попадает на продолжение отрезка .

Если необходимо найти координаты основания перпендикуляра CN, то поступают следующим образом.

Пусть a*x+b*y+c=0 уравнение прямой AB.Найдем уравнение прямой проходящей через точку С перпендикулярно прямой AB. Вектор n1, перпендикулярный прямой AB, имеет координаты (a,b). Вектор n2, перпендикулярный прямой CN, имеет координаты (-b, a).Так как эти векторы перпендикулярны и их скалярное произведение должно равняться нулю.

a*(-b)+b*a=0. Тогда уравнение прямой CN имеет вид –bx+ay+c1=0. Если точка принадлежит прямой , то ее координаты обращают уравнение этой прямой в истинное числовое равенство. Подставляем координаты точки N в уравнение прямой и получаем

-b*x0+a*y0+c1=0 откуда c1=b*x0-a*y0. И искомое уравнение –b*x+a*y+b*x0-a*y0=0.

Решаем систему уравнений

a *x+b*y+c=0

–b*x+a*y+b*x0-a*y0=0

и находим координаты точки N. Для выяснения вопроса о принадлежности точки отрезку или его продолжению проверим выполнение следующих условий, рассматривая два случая.

A N B N A B

AN+NB+AB AN+NB>AB

Program otrezok;

Type TSegment = Record

X1, Y1, X2, Y2: Longint;

End;

Var X, Y: Longint;

S: TSegment;

Function VectMul(X1, Y1, X2, Y2: Longint): Longint;

Begin

VectMul := X1 * Y2 - X2 * Y1;

End;

Function ScalMul(X1, Y1, X2, Y2: Longint): Longint;

Begin

ScalMul := X1 * X2 + Y1 * Y2;

End;

Function Len(X1, Y1, X2, Y2: Longint): Extended;

Begin

Len := Sqrt(Sqr(X1 - X2) + Sqr(Y1 - Y2));

End;

Begin

assign(input, 'input');reset(input);

assign(output, 'output.txt'); rewrite(output);

Read(X, Y, S.X1, S.Y1, S.X2, S.Y2);

If (ScalMul(S.X2 - S.X1, S.Y2 - S.Y1, X - S.X1, Y - S.Y1) > 0) and

(ScalMul(S.X1 - S.X2, S.Y1 - S.Y2, X - S.X2, Y - S.Y2) > 0)

Then

Write(Abs(VectMul(S.X1 - X, S.Y1 - Y, S.X2 - X, S.Y2 - Y)) / Len(S.X1, S.Y1, S.X2, S.Y2):0:5)

Else

If Len(X, Y, S.X1, S.Y1) < Len(X, Y, S.X2, S.Y2)

Then

Write(Len(X, Y, S.X1, S.Y1):0:5)

Else

Write(Len(X, Y, S.X2, S.Y2):0:5);

Close(Input);

Close(Output);

End.

Расстояние между двумя фигурами

Опр. Расстоянием между фигурами называется наименьшее расстояние между точками этих фигур.

Например ,

Для того чтобы найти расстояние между двумя отрезками надо найти расстояние от концов первого отрезка до второго , от концов второго до первого и выбрать наименьшее.

На одной из олимпиад предлагалась следующая задача.

Задача 18 Замки

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

Входные данные:

В первой строке входного файла записано целое число m (1<m<20) - количество вершин многоугольника, изображающего первый замок. Каждая из последующих m строк содержит по два вещественных числа x , y

(–1000000<x<1000000 , –1000000<y<1000000 ) - координаты вершин многоугольника, изображающего первый замок, в порядке обхода вершин по часовой стрелке. Затем в таком же формате количество вершин и координаты вершин многоугольника, изображающего второй замок.

Выходные данные:

В выходной файл записать минимальную длину подземного хода между замками, округлив результат с точностью до тысячных.

Примеры

Input.txt	Output.txt
4 0.000 0.000 0.000 1.000 1.000 1.000 1.000 0.000 3 2.000 0.000 3.000 3.000 4.000 0.000	1.000

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

Задача 19 Пересечение двух отрезков

Даны два отрезка. Пересекаются ли эти отрезки.

Входные данные:

Восемь целых чисел — координаты начала и конца двух отрезков.

Выходные данные:

Одна строка "YES", если отрезки имеют общие точки, и "NO" в противном случае.

Пример

Input.txt	Output.txt
51261178	YES

Program otrezki;

Type

TLine = Record

X1, Y1, X2, Y2: Longint;

End;

Var A, B: TLine;

i:integer;s:string;

Function VM(X1, Y1, X2, Y2: Longint): Shortint;

Var X: Extended;

Begin

X := 1.0 * X1 * Y2 - 1.0 * X2 * Y1;

If X < 0 Then

VM := - 1

Else

If X > 0 Then VM := 1

Else VM := 0;

End;

Procedure Swap(var A, B: Longint); обменивает значения двух переменных

Var C: Longint;

Begin

C := A;

A := B;

B := C;

End;

Function Cross: Boolean;

Begin

If A.X1 > A.X2 Then Swap(A.X1, A.X2);

If A.Y1 > A.Y2 Then Swap(A.Y1, A.Y2);

If B.X1 > B.X2 Then Swap(B.X1, B.X2);

If B.Y1 > B.Y2 Then Swap(B.Y1, B.Y2);

Cross := not ((B.X2 < A.X1) or (B.X1 > A.X2)) and

not ((B.Y2 < A.Y1) or (B.Y1 > A.Y2));

End;

Begin

assign(input, 'input');reset(input);

assign(output, 'output.txt'); rewrite(output);

Read(A.X1, A.Y1, A.X2, A.Y2, B.X1, B.Y1, B.X2, B.Y2);

If (VM(A.X2 - A.X1, A.Y2 - A.Y1, B.X1 - A.X1, B.Y1 - A.Y1) *

VM(A.X2 - A.X1, A.Y2 - A.Y1, B.X2 - A.X1, B.Y2 - A.Y1) <= 0) and

(VM(B.X2 - B.X1, B.Y2 - B.Y1, A.X1 - B.X1, A.Y1 - B.Y1) *

VM(B.X2 - B.X1, B.Y2 - B.Y1, A.X2 - B.X1, A.Y2 - B.Y1) <= 0) and

Cross Then Write('YES')

Else Write('NO');

Close(Input);

Close(Output);

End.

Задача 20 Пересечение двух прямых

Взаимное расположение двух прямых.

Пусть прямые заданы уравнениями a1*x+b1*y+c1=0 и a2*x+b2*y+c2=0.

Могут быть три случая:

a1/a2=b1/b2=c1/c2 прямые совпадают

a1/a2=b1/b2<>c1/c2 прямые параллельны

a1/a2<>b1/b2 прямые пересекаются

Для нахождения координат точки пересечения прямых надо решить систему уравнений:

a 1*x+b1*y+c1=0 x=(b1*c2-c1*b2*)/(a1*b2-a2*b1)

a2*x+b2*y+c2=0 y=(a2*c1-a1*c2*)/(a1*b2-a2*b1)

Формат входных данных

Шесть чисел — коэффициенты А, В и С общего уравнения двух различных непараллельных прямых (сначала для одной прямой, затем для другой).

Формат выходных данных

Два числа — координаты точки их пересечения.

Пример

Input.txt	Output.txt
1 1-1 1-1 0	0.5 0.5

В программе рассматривается случай пересечения двух прямых.

Program peres;

Var A1, B1, C1, A2, B2, C2: Longint;

Begin

assign(input, 'input');reset(input);

assign(output, 'output.txt'); rewrite(output);

Read(A1, B1, C1, A2, B2, C2);

Write((C1 * B2 - B1 * C2) / (B1 * A2 - A1 * B2):0:5, ' ', (A1 * C2 - C1 * A2) / (B1 * A2 - A1 * B2):0:5);

Close(Input);

Close(Output);

End.

Задача 21 Биссектриса угла

Угол задан тремя точками X, Y и Z. Найти уравнение биссектрисы этого угла.

Формат входных данных

Шесть чисел — координаты точек X, Y и Z.

Формат выходных данных

Три числа — коэффициенты общего уравнения биссектрисы угла LYXZ.

Пример

Input.txt	Output.txt
1110 0 1	-1.0 1.0 0.0

Type

TPoint = Record

X, Y: Extended;

End;

Var

A, B, C, A1, B1, C1: TPoint;

Function Len(A, B: TPoint): Extended;

Begin

Len := Sqrt(Sqr(A.X - B.X) + Sqr(A.Y - B.Y));

End;

Procedure Normal(A, B: TPoint; var C: TPoint);

Var L: Extended;

Begin

L := Len(A, B);

C.X := A.X + (B.X - A.X) / L;

C.Y := A.Y + (B.Y - A.Y) / L;

End;

Procedure WriteOut(X1, Y1, X2, Y2: Extended);

Var A, B, C: Extended;

Begin

A := Y2 - Y1;

B := X1 - X2;

C := - A * X1 - B * Y1;

Write(A:0:6, ' ', B:0:6, ' ', C:0:6);

End;

Begin

assign(input, 'input');reset(input);

assign(output, 'output.txt'); rewrite(output);

Read(A.X, A.Y, B.X, B.Y, C.X, C.Y);

Normal(A, B, B1);

Normal(A, C, C1);

A1.X := B1.X - A.X + C1.X;

A1.Y := B1.Y - A.Y + C1.Y;

WriteOut(A.X, A.Y, A1.X, A1.Y);

Close(Input);

Close(Output);

End.

Задача 22 Касательная к окружности

Дана окружность и точка вне ее. Из точки проведена касательная к окружности. Найти координаты точек касания.

Формат входных данных

Пять чисел — координаты центра и радиус окружности, координаты точки.

Формат выходных данных

Координаты точек касания.

Пример

Input.txt	Output.txt
1112 2	2 1 2 2 1

Const

E = 1e-7;

Type

TCircle = Record

X, Y, R: Extended;

End;

TPoint = Record

X, Y: Extended;

End;

Var

C: TCircle;

A, P, N1, N2: TPoint;

L1, L2, H, D: Extended;

Function Len(X1, Y1, X2, Y2: Extended): Extended;

Begin

Len := Sqrt(Sqr(X1 - X2) + Sqr(Y1 - Y2));

End;

Begin

assign(input, 'input');reset(input);

assign(output, 'output.txt'); rewrite(output);

Read(C.X, C.Y, C.R, A.X, A.Y);

L1 := Len(C.X, C.Y, A.X, A.Y);

If L1 < C.R - E Then

Writeln('0')

Else

If Abs(L1 - C.R) < E Then Begin

Writeln('1');

Writeln(A.X:0:5, ' ', A.Y:0:5)

End Else Begin

L2 := Sqrt(L1 * L1 - C.R * C.R);

H := C.R * L2 / L1;

D := C.R * C.R / L1; //D := C.R * H / L2;

N1.X := (A.X - C.X) / L1;

N1.Y := (A.Y - C.Y) / L1;

N2.X := -N1.Y;

N2.Y := N1.X;

P.X := C.X + N1.X * D;

P.Y := C.Y + N1.Y * D;

Writeln('2');

Writeln(P.X + N2.X * H:0:5, ' ', P.Y + N2.Y * H:0:5);

Writeln(P.X - N2.X * H:0:5, ' ', P.Y - N2.Y * H:0:5);

End;

Close(Input);

Close(Output);

End.

Задача 23 Окружность и прямая

Дана окружность и прямая. Определить количество точек пересечения окружности и прямой.

Формат входных данных

Шесть чисел — координаты центра и радиус окружности и коэффициенты А, В и С нормального уравнения прямой.

Формат выходных данных

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

Пример

Input.txt	Output.txt
1 1 1 1-1 0	2 1.70711 1.70711 0.29289 0.29289

Const

E = 1e-7;

Type

TCircle = Record

X, Y, R: Longint;

End;

TLine = Record

A, B, C: Longint;

End;

TPoint = Record

X, Y: Extended;

End;

Var

C: TCircle;

P: TPoint;

L: TLine;

R, S, D, F: Extended;

Begin

assign(input, 'input');reset(input);

assign(output, 'output.txt'); rewrite(output);

Read(C.X, C.Y, C.R, L.A, L.B, L.C);

S := Sqrt(L.A * L.A + L.B * L.B);

R := Abs(L.A * C.X + L.B * C.Y + L.C) / S;

If R > C.R + E Then

Writeln('0')

Else Begin

F := (L.A * C.X + L.B * C.Y + L.C) / (L.A * L.A + L.B * L.B);

P.X := C.X - L.A * F;

P.Y := C.Y - L.B * F;

If Abs(R - C.R) < E Then Begin

Writeln('1');

Writeln(P.X:0:5, ' ', P.Y:0:5);

End Else Begin

D := Sqrt(C.R * C.R - Sqr(L.A * C.X + L.B * C.Y + L.C) / (L.A * L.A + L.B * L.B));

Writeln('2');

Writeln(P.X - L.B / S * D:0:5, ' ', P.Y + L.A / S * D:0:5);

Writeln(P.X + L.B / S * D:0:5, ' ', P.Y - L.A / S * D:0:5);

End;

End;

Close(Input);

Close(Output);

End.

Задача 24 Две окружности

Найти количество общих точек двух окружностей.

Формат входных данных

Шесть чисел — координаты центра и радиусы двух окружностей.

Формат выходных данных

В случае если количество общих точек окружностей конечно, в первой строке вывести одно число К, равное этому количеству, далее в К строках координаты самих точек. Если указанных точек бесконечно много, вывести единственное число "3".

Пример

Input.txt	Output.txt
2 3 13 2 1	2 3.0 3.0 2.0 2.0

Const

E = 1e-7;

Type

TCircle = Record

X, Y, R: Longint;

End;

TPoint = Record

X, Y: Extended;

End;

Var

C1, C2: TCircle;

P, R: TPoint;

D1, D, H: Extended;

Begin

assign(input, 'input');reset(input);

assign(output, 'output.txt'); rewrite(output);

Read(C1.X, C1.Y, C1.R, C2.X, C2.Y, C2.R);

R.X := C2.X - C1.X;

R.Y := C2.Y - C1.Y;

D := Sqrt(R.X * R.X + R.Y * R.Y);

If Abs(D) < E Then

If Abs(C1.R - C2.R) < E Then Writeln('3')

Else Writeln('0')

Else Begin

D1 := ((C1.R * C1.R - C2.R * C2.R) / D + D) / 2;

If D1 > C1.R Then

Writeln('0')

Else Begin

H := Sqrt(C1.R * C1.R - D1 * D1);

P.X := C1.X + R.X / D * D1;

P.Y := C1.Y + R.Y / D * D1;

If Abs(H) < E Then Begin

Writeln('1');

Writeln(P.X:0:5, ' ', P.Y:0:5);

End Else Begin

Writeln('2');

Writeln(P.X - R.Y / D * H:0:5, ' ', P.Y + R.X / D * H:0:5);

Writeln(P.X + R.Y / D * H:0:5, ' ', P.Y - R.X / D * H:0:5);

End;

End;

End;

Close(Input);

Close(Output);

End.

Задача 25 Длина дуги

Найти длину дуги.

Формат входных данных

Семь чисел — координаты центра и радиус окружности и вещественные координаты двух точек на ней, с точностью до пятого знака после запятой.

Формат выходных данных

Одно вещественное число — длина меньшей дуги окружности заключённой между указанными точками.

Пример

Input.txt	Output.txt
1 1 1 2.0 1.0 1.0 2.0	1.57080

Const

E = 1e-7;

Type

TPoint = Record

X, Y: Extended;

End;

Var

X, Y, R, S, C: Extended;

La, Lb: Extended;

A, B: TPoint;

Function VectMul(X1, Y1, X2, Y2: Extended): Extended;

Begin

VectMul := X1 * Y2 - X2 * Y1;

End;

Function ScalMul(X1, Y1, X2, Y2: Extended): Extended;

Begin

ScalMul := X1 * X2 + Y1 * Y2;

End;

Function Len(X1, Y1, X2, Y2: Extended): Extended;

Begin

Len := Sqrt(Sqr(X1 - X2) + Sqr(Y1 - Y2));

End;

Begin

assign(input, 'input');reset(input);

assign(output, 'output.txt'); rewrite(output);

Read(X, Y, R, A.X, A.Y, B.X, B.Y);

If Abs(R) < E Then

Write(0)

Else Begin

La := Len(A.X, A.Y, X, Y);

Lb := Len(B.X, B.Y, X, Y);

S := VectMul(A.X - X, A.Y - Y, B.X - X, B.Y - Y) / La / Lb;

C := ScalMul(A.X - X, A.Y - Y, B.X - X, B.Y - Y) / La / Lb;

If C = 0 Then

Write(Pi * R / 2:0:5)

Else

If (S = 0) and (C < 0) Then Write(Pi * R:0:5)

Else Write(ArcTan(Abs(S) / C) * R:0:5);

End;

Close(Input);

Close(Output);

End.

Любую фигуру на плоскости мы будем рассматривать как множество точек на плоскости. В частности фигура может состоять и из одной точки.

Опр. Уравнением линии на плоскости называется уравнение, связывающее x и y, такое что его обращают в истинное числовое равенство координаты точек принадлежащих линии и никакие другие.

Линию можно задать :

в явном виде y=f(x)

в неявном виде f(x,y)=0

в параметрическом виде x=r(t), y=h(t) где a<t<b

4) в полярной системе координат f(r,)=0

Геометрические преобразования.

К геометрическим преобразованиям относятся параллельный перенос, поворот вокруг точки, центральная симметрия относительно точки, осевая симметрия относительно прямой, гомотетия относительно точки. Запишем формулы по которым происходит преобразование координат точек фигуры.

Задача 26 Параллельный перенос на вектор AB

А(x,y) B(x1,y1)

x1:=x+a где (a,b)-координаты вектора AB.

y1:=y+b

Задача 27 Поворот вокруг точки на угол 

A(x,y)

x1=x0+(x-x0)cos- (y-y0)sin

 y1=y0+(x-x0)sin+ (y-y0cos)

B(x1,y1)

О(x0,y0)

Задача 28 Центральная симметрия

O(x0,y0)

A(x,y) B(x1,y1)

Так как векторы AO и OB равны, то их координаты тоже равны.

x 0-x=x1-x0

y0-y=y1-y0

отсюда x1=2*x0-x

y1=2*y0-y

Задача 29 Осевая симметрия относительно прямой ax+by+c=0

A(x,y)

O

B(x1,y1)

Задача 30 Гомотетия

Опр. Гомотетией относительно точки О называется преобразование

плоскости, при котором все расстояния от точки О до точек фигуры изменяются в к раз.

O(x₀,y₀) A(x,y B(x₁,y₁) Вектор OB=k*OA

В координатах x-x₀=k*(x₁-x₀) отсюда x₁=x₀+k*(x-x₀)

y-y₀=k*(y₁-y₀) y₁=y₀+k*(y-y₀)

Если k>0 то точки А и В лежат по одну сторону от точки О, если k<0 то по разные.

Рассмотрим несколько задач на геометрические преобразования.

Задача 31 Симметричная точка

Дана прямая и точка вне ее. Построить точку симметричную данной относительно прямой.

Найдем общее уравнение прямой AB, перпендикулярной данной прямой и проходящей через данную точку A(x,y). Мы это уже умеем делать.

Пусть уравнение прямой AB a₁x+b₁y+c₁=0

Решаем систему уравнений и находим координаты точки O(x0,y0).

ax+by+c=0

a₁x+b₁y+c₁=0

Так как точка О середина отрезка AB, то по формуле координат середины отрезка находим координаты искомой точки.

x₁=2*x₀-x

y₁=2*y₀-y

Задача 32 Вершина квадрата

Даны три вершины квадрата АВС. Найти координаты четвертой вершины и построить квадрат.

Алгоритм решения достаточно простой. Находим координаты центра квадрата по формуле координат середины отрезка. И по этой же формуле находим координаты четвертой вершины квадрата.

Задача 33 Симметричеый треугольник 1

Дан треугольник АВС с координатами вершин А(x1,y1), B(x2,y2), C(x3,y3) и точка О(x0,y0). Построить треугольник симметричный данному относительно точки О.

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

Задача 34 Симметричеый треугольник 2

Дан треугольник АВС с координатами вершин А(x1,y1), B(x2,y2), C(x3,y3) и точки M(x4,y4), N(x5,y5). Построить треугольник симметричный данному относительно прямой MN.

Задача 35 Калейдоскоп

Дан рисунок прямоугольного треугольника ABC. Последовательно отображая его сначала симметрично относительно гипотенузы AB, затем симметрично относительно стороны BC, затем относительно MN, получить следующую картинку. Орнаменты могут быть различными.

A C

M N

B

Решение: Выгодно расположить прямоугольный треугольник ABC так, чтобы его гипотенуза лежала на биссектрисе первой четверти системы координат экрана.

x

(y,x)

y (x,y)

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

for i:=0 to l do

begin

for j:=1 to i do

begin

putpixel(x-j,y-i,getpixel(y-i,x-j));

end;

end;

Симметрию относительно вертикальной прямой x=x0 осуществляем следующим образом:

(x0-i,y) (x0+i,y)

x=x0

Симмтетрию относительно горизонтальной прямой y=y0

(x,y0-j)

y=y0

(x,y0+j)

Задача 36 Заполнение экрана

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

Задача 37 Восстановление координат вершин треугольника

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

Ввести в одной строке через один пробел 6 целых чисел координаты середин сторон треугольника по обходу по часовой стрелке x1,y1,x2,y2,x3,y3 (-100<= x1,y1,x2,y2,x3,y3<=100).

Вывести в одной строке через один пробел координаты вершин треугольника x4,y4,x5,y5,x6,y6.

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

Input.txt	Output.txt
0 0 3 3 3 0	0 3 6 3 0 -3

Используем формулу нахождения координат середины отрезка. Получим систему линейных уравнений

2 *x1=x4+x6;

2*y1=y4+y6;

2*x2=x4+x5;

2*y2=y4+y5;

2*x3=x5+x6;

2*y3=y5+y6;

Система легко решается методом сложения.

Задача 38 Задание множества точек на плоскости неравенствами

Полуплоскость задается неравенствами ax+by+c>=0 или ax+by+c<=0.

Первое неравенство задает полуплоскость, лежащую выше прямой или правее, если прямая вертикальна, а второе ниже или левее.

Множество точек квадрата можно

1 задать как пересечение четырех

полуплоскостей. Т.е. квадрат

задается системой из четырех

-1 1 неравенств

-1 -x+y-1<=0

x+y-1<=0

-x+y+1>=0

x+y+1>=0

Вообще условий в системе должно быть столько, сколько различных линий ограничивают фигуру.

Круг с центром в начале координат и радиусом R задается неравенством x²+y²<=R^2.

С центром в точке (x0,y0) неравенством (x-x₀)²+(y-y₀)²<=R²

Задача 39 Множество точек

Каким условием можно задать множество точек

Для этой фигуры приходится использовать

составное условие, так как точка

принадлежит треугольнику или

-1 1 первой четвертинке круга.

((y-x-1<=0)and(y>=0)and(x<=0))

or((x²+y²<=1)and(y>=0)and(x>=0))

Технология решения олимпиадных задач по вычислительной геометрии имеет свою специфику. Покажем ее на примере решения следующей задачи.

Задача 40 Продолжение отрезка

На экране монитора изображен отрезок белого цвета. Продолжить его в обе стороны до пересечения с границами экрана красным цветом.

Исходные данные: две пары целых чисел x1,y1 и x2,y2.

0<=xi<=640, 0<=yi<=480, i=1,2.

O(0,0) 640

Размеры экрана 640*480.Начало

X координат находится в левом

B(x2,y2) верхнем углу экрана, ось ОХ

Y направлена вправо, ось ОY вниз.

480 A(x1,y1)

Алгоритм решения:

1) Найдем уравнение прямой AB.

ax+by+c=0

2) Изменяя x от 0 до x1 с, шагом 1, вычисляем y из уравнения прямой AB и рисуем на экране точки с координатами (x,y) красным цветом.

3) Изменяя x от x2 до 640 с, шагом 1, вычисляем y из уравнения прямой AB и рисуем на экране точки с координатами (x,y) красным цветом.

Пишем программу , запускаем ее на выполнение, видим на экране нужную картину и.. самое время задать вопрос: решена ли задача? Вроде бы –да, но попробуем ввести сначала координаты точки B, а потом точки A. Запускаем программу и видим, что наш белый отрезок исчез. Красные лучи перекрыли друг друга. Следовательно, необходимо, чтобы x1 было меньше.x2.Значит после ввода данных надо меньшее из абсцисс данных точек поместить в x1, не забыв поменять и ординаты. Это делается через третью переменную

2

X1 x2 p:=x1;x1:=x2;x2:=p;, хотя можно

и без использования вспомогательной

1 3 переменной x1:=x2-x1;x2:=x2-x1;x1:=x1+x2

P

Пробуем оба варианта. Все нормально, и задаем себе все тот же вопрос – решена ли задача? Пробуем вертикальный отрезок и.. ничего не рисуется, кроме самого отрезка. Уравнение вертикальной прямой x=c/а, в уравнении отсутствует переменная y и мы не можем выполнить второй и третий шаги алгоритма. Догадываемся, что в этом случае надо в качестве параметра цикла брать y а не x. Придется в программу вводить ветвление. Если x1=x2 то запускаем циклы по параметру y,причем в первом цикле y меняется от 480 до y2, а во втором от y1 до 0,а иначе по параметру x. Еще не забудем поместить меньшую ординату в переменную y1. И только теперь, проверив все варианты возможного расположения отрезка, мы можем быть уверены, что программа работает правильно. Вот эти всевозможные варианты образуют так называемую полную систему тестов. Придумать полную систему тестов для конкретной задачи не так просто, как может показаться. Для этого надо проводить специальные тренировки.

Задача 41 Куда идем мы с Пятачком?

“Кто ходит в гости по утрам, тот поступает мудро…”

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

Напишите программу, которая посчитает длину самого короткого безопасного пути от домика Винни-Пуха до домика Кролика.

Ловушка для Слонопотама представляет собой яму абсолютно круглой формы. Путь является безопасным, если он не проходит по ловушке (но может проходить по ее границе).

Входные данные

Во входном файле записаны сначала координаты домика Винни-Пуха X_В Y_В, затем — координаты домика Кролика X_К Y_К, а затем — координаты центра и радиус ловушки X_Л Y_Л R_Л. Все координаты — целые числа из диапазона от –32000 до 32000. Радиус ловушки — натуральное число, не превышающее 32000.

Домики Винни-Пуха и Кролика не могут находиться внутри ловушки, но могут находиться на ее границе.

Выходные данные

Выведите в выходной файл одно число — длину самого короткого безопасного пути от домика Винни-Пуха до домика Кролика с тремя знаками после десятичной точки.

Примеры

Input.txt	Output.txt
0 0 0 1 10 10 1	1.000
5 0 0 5 0 0 5	7.854
-5 0 5 0 0 0 3	11.861

Могут быть три случая:

1) угол AON +угол BOM > угла AOB

Искомое расстояние AB=SQRT((x2-x1)2+(y2-y1)2)

2) угол AON +угол BOM < угла AOB

Искомое расстояние=AN + длина дуги MN + MB

AN²=AO² -R²

BM²=BO² -R²

MN=R* alf

Случай когда точки А и В лежат на окружности является частным случаем 2-го.

3) угол AON +угол BOM = углу AOB

Искомое расстояние AB

Program pytachok;

Const eps=1e-3;

Type real=extended;

tpoint=record

x,y:real;

end;

var a,b,o:tpoint;

r,res:real;

procedure init;

begin

assign(input,'a.in'); reset(input);

read(a.x,a.y,b.x,b.y,o.x,o.y,r);

end;

Function Rast2point(a,b:tpoint):real; функция, вычисляющая раастояние между 2 точками

begin

Rast2point:=sqrt(sqr(a.x-b.x)+sqr(a.y-b.y));

end;

function realeq(a,b:real):boolean; функция, проверяющая равенство двух чисел

begin

realeq:=(abs(a-b)<=eps);

end;

function realmore(a,b:real):boolean; функция, проверяющая неравенство a>b

begin

realmore:=(a-b)>eps;

end;

function realless(a,b:real):boolean; функция, проверяющая неравенство a<=b

begin

realless:=(b-a)>eps;

end;

function realeq_more(a,b:real):boolean; функция, проверяющая неравенство a>=b

begin

realeq_more:=(realeq(a,b))and(realmore(a,b));

end;

function realeq_less(a,b:real):boolean;

begin

realeq_less:=(realeq(a,b))or(realless(a,b));

end;

procedure solve;

var fi,alpha,betta,tmpsin,tmpcos,p:real;

begin

tmpcos:=(sqr(rast2point(o,b))+sqr(rast2point(o,a))-sqr(rast2point(a,b)))/

(2*rast2point(o,b)*rast2point(o,a)); вычисление величины угла АОВ

tmpsin:=sqrt(1-sqr(tmpcos));

if realeq(tmpcos,0) then fi:=pi/2 else

begin

if realeq_less(tmpcos,0) then p:=pi else p:=0;

fi:=arctan(tmpsin/tmpcos)+p;

end;

вычисление величины угла BOM

tmpcos:=(sqr(rast2point(a,o))+sqr(r)-sqr(sqrt(sqr(rast2point(a,o))-sqr(r))))/(2*rast2point(a,o)*r);

tmpsin:=sqrt(1-sqr(tmpcos));

if realeq(tmpcos,0) then alpha:=pi/2 else

begin

if realeq_less(tmpcos,0) then p:=pi else p:=0;

alpha:=arctan(tmpsin/tmpcos)+p;

end;

вычисление величины угла BON tmpcos:=(sqr(rast2point(b,o))+sqr(r)-sqr(sqrt(sqr(rast2point(b,o))-sqr(r))))/(2*rast2point(b,o)*r);

tmpsin:=sqrt(1-sqr(tmpcos));

if realeq(tmpcos,0) then betta:=pi/2 else

begin

if realeq_less(tmpcos,0) then p:=pi else p:=0;

betta:=arctan(tmpsin/tmpcos)+p;

end;

if realeq_less(fi,alpha+betta) then res:=rast2point(a,b)else сравниваем углы и вычисляем

begin искомое расстояние

res:=sqrt(sqr(rast2point(o,a))-sqr(r))+

sqrt(sqr(rast2point(o,b))-sqr(r))+

(fi-(alpha+betta))*r;

end;

end;

procedure out;

begin

assign(output,'a.out'); rewrite(output);

write(res:0:3); close(output);

end;

begin init; solve; out; end.

Задача 42 Ломаная линия

На плоскости расположено N (2N512) точек, пронумерованных от 1 до N. Каждая точка описывается двумя целочисленными координатами x_i и y_i. Любые две точки не совпадают. Ваша задача найти координаты замкнутой ломаной линии без самопересечений, проходящей через все точки, и выдать номера точек в порядке обхода.

Входные данные.

Первая строка файла содержит число N – количество точек. Затем в следующих N строках записаны координаты точек x_i и y_i .

Выходные данные.

Выходной файл содержит номера точек в порядке обхода.

Input.txt	Output.txt
4 0 0 0 1 1 1 1 0	1 2 3 4

Задача 43 Проверка принадлежности точки треугольнику

Для треугольника существует стандартный алгоритм, который надо знать, хотя и более общий тоже годится.

Определение принадлежности точки треугольнику. Точка принадлежит треугольнику, если она лежит внутри него или на стороне. Для определения принадлежности точки M(x0,y0)треугольнику ABC используется следующий алгоритм: вся плоскость делится прямой , проходящей через вершину треугольника и заданную точку, на две полуплоскости.

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

A(x1,y1)

M

C(x3,y3)

B(x2,y2)

Проверяем прямую AM

Hаходим её уравнение ax+by+c=0 по двум точкам A и M.

Рассмотрим функцию двух переменных F(x,y)= ax+by+c; Если точка B и точка C лежат в разных полуплоскостях, то произведение

F(x2,y2)*F(x3,y3)<=0 и если точки B и A лежат по разные стороны относительно прямой CM, то F(x2,y2)*F(x1,y1)<=0;

Таким образом

if (F(x2,y2)*F(x3,y3)<=0)and(F(x2,y2)*F(x1,y1)<=0)

then writeln(‘Точка принадлежит треугольнику’)

else writeln(‘Точка не принадлежит треугольнику’)

Задача 44 Проверка принадлежности точки выпуклому многоугольнику

Опр.Многоугольник называется выпуклым, если все его вершины расположены по одну сторону от любой прямой содержащей стороны многоугольника.

Центр тяжести выпуклого многоугольника всегда находится внутри этого многоугольника. Координаты центра тяжести находятся как среднее арифметическое координат вершин многоугольника.

x₀=(x₁+x₂+..x_n)/n

y₀=(y₁+y₂+..y_n)/n

Теперь дадим общий алгоритм проверки принадлежности точки выпуклому многоугольнику.

Пусть (x₁,y₁), (x₂,y₂), ... ,(x_n,y_n) - координаты вершин многоугольника на плоскости .Координаты вершин заданы в порядке обхода многоугольника по часовой или против часовой стрелки. Для определенности возьмем по часовой. Для удобства вводим фиктивную вершину (x_n+1,y_n+1), такую что x_n+1 =x_1, y_n+1 = y₁

X_o,Y_o - координаты данной точки,

Далее в цикле находим знак Zi=Sign(Vi) для каждого из векторных произведений

Vi=(Xi₊₁-Xi)*(Y_o-Yi)-(X_o-Xi)*(Yi₊₁-Yi) i=1..n.

A2

A1

A3

A5 O

A4

Напомним что векторное произведение векторов равно удвоенной площади ориентированного треугольника. Таким образом, если точка внутри, то обход треугольников всегда будет идти по часовой стрелке и знаки векторных произведений всегда будут одинаковы. Если точка снаружи - будет хоть одно несовпадение. Если точка на стороне от i к i+1-oй вершине - Vi=0.

Задача 45 Проверка принадлежности точки произвольному многоугольнику

Д ан многоугольник A₁A₂..A_n и точка P(x0,y0). Определить, принадлежит ли точка Р многоугольнику. Точка считается принадлежащей многоугольнику, если она лежит внутри него или на границе. Проведем луч из точки Р вправо.

P Q E B C D E

Рис1.Точек пересечений шесть.

Р E B C A D

Рис2. Точек пересечений пять.

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

Ситуация с вершиной A. Обе стороны, имеющие общую вершину, лежат по одну сторону от проведенного луча. В это случае количество пересечений будем считать равным нулю.

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

Ситуация со стороной ВС. Проведенный луч проходит по стороне. В этом случае число пересечений будем считать равным 0.

Ситуация с вершиной Е. Луч пересекает сторону во внутренней точке. В этом случае одно пересечение.

Далее подсчитываем количество пересечений луча со сторонами по вышеописанным правилам. Если число пересечений четное, то точка снаружи, если нечетное ,то внутри.

Задача 46 Прямая и окружность

Любые уравнения прямой и окружности могут быть приведены к следующему каноническому виду:

(1) Прямая (X-X₁)(Y₂-Y₁)=(Y-Y₁)(X₂-X₁) (2) и окружность (X-X₀)²+(Y-Y₀)²=R² 1. Проверяем случай X₂ = X₁ - тогда прямая вертикальна: уравнение (1) имеет вид X = X₁. Подставляем X₁ в уравнение (2): (Y-Y₀)²=R² - (X₁-X₀)². Это квадратное уравнение и количество корней (точек пересечения прямой и окружности) зависит от знака дискриминанта. Корни этого уравнения - ординаты точек пересечения.

2. Если X₂ =/= X₁, то, разделив на это обе части (1) на X₂-X₁ , имеем: Y=KX + B - новый вид уравнения прямой. K и B выражаются через X_1,2 и Y_1,2. Подставляем этот Y в уравнение (2) - имеем квадратное уравнение относительно X. Находим дискриминант и по его знаку выясняем количество точек пересечения.

if R² > (X₁-X₀)² 2 точки пересечения.

if R² == (X₁-X₀)² 1 точка пересечения.

if R² < (X₁-X₀)² пересечений нет.

Задача 47 Соединение точек простой замкнутой ломаной

N точек на плоскости заданы своими координатами. Найти порядок, в котором можно соединить эти точки, чтобы получился N-угольник (т.е. не было бы пересечений сторон).

Рассмотрим два из возможных алгоритмов.

Вариант 1. Строим выпуклую оболочку данного множества точек. Если все точки множества A лежат на контуре, то задача решена. Если же нет, то ищем точку l с минимальным расстоянием до контура -- пусть это минимальное расстояние до стороны фигуры (u,v) (если таких точек несколько, то берем любую из них), вставляем в контур точку l (вместо контура ... u,v ... будет ... u,l,v, ...).Для оставшихся точек повторяем описанную выше процедуру, пока последняя не будет вставлена в контур.

Вариант 2. Строим выпуклую оболочку V данного множества точек.

Если все точки множества A лежат на контуре, то задача решена. Иначе обозначим через A₁ все внутренние точки выпуклой оболочки V. Строим для нового множества A₁ выпуклую оболочку V₁ (контуры V и V₁ не пересекаются!).

"Склеиваем" два контура:

Выберем по паре последовательных вершин p,s и p₁,s₁ на контурах V и V₁ соответственно так, чтобы в четырехугольнике с вершинами s,p,p₁,s₁ не лежало больше никаких других точек контуров V и V₁. Разрываем контуры V и V₁ (убирая ребра (p,s) и (p₁,s₁)) и объединяем их (добавляя ребра (p,p₁) и (s,s₁)).

Если внутри V₁ нет внутренних точек, то задача решена, иначе же с внутренними точками V₁ проделываем те же самые операции: находим выпуклую оболочку и пары последовательных точек на контурах, разрываем и склеиваем контуры, и т.д., пока не получим, что последняя построенная выпуклая оболочка содержит в себе 0, 1 или 2 точки.

Если точек 0, то задача решена. В противном случае присоединяем точки к ранее образованному контуру так, чтобы фигура осталась многоугольником (можно проводить присоединение, как и в варианте 1).

Взаимное расположение двух окружностей.

Могут быть следующие случаи взаимного расположения двух окружностей с радиусами R1 и R2:

A B A B

AB>R1+R2 AB=R1+R2

A B

A B

AB<R1+R2 AB=R2-R1

A B A=B

AB<R2-R1 (x1=x2)and(y1=y2)and(R1<R2)

Задача 48 Нахождение длины общей касательной для двух окружностей

AB=O₁C; O₂C=R₁-R₂

B Из прямоугольного

треугольника O₁O₂C

A C

O₂ O₂C=SQRT(O₁O₂²-(R1-R2)²)

O₁

Задача 49 Тропинка

В лесу между деревьями необходимо проложить тропинку наибольшей ширины. Тропинка представляет из себя полосу. Направление тропинки задается вектором n(x,y). У нас есть план леса-вид сверху, на котором деревья изображаются в виде окружностей с заданными координатами центров и радиусами. Найти наибольшую ширину тропинки с точностью трех знаков после десятичной точки.

Входные данные

Во входном файле записаны сначала количество n>1 деревьев в лесу, затем — целочисленные координаты вектора n(X0, Y0), а затем — координаты центра и радиус каждого дерева Xi Yi Ri. Все координаты — целые числа из диапазона от –32000 до 32000.

Выходные данные

Выведите в выходной файл одно число — ширину самой широкой тропинки с тремя знаками после десятичной точки или слово “no”, если провести тропинку нельзя.

Примеры

Input.txt	Output.txt
2 0 1 10 20 30 30 40 10	No
2 0 1 10 20 5 40 50 5	20.000

l(a1,b1)

n(a,b)



x₁₁ x₁ x₂₁ x₁₂ x₂ x₂₂ x₁₃ x₃ x₂₃

Алгоритм решения.

Если вектор n направлен параллельно оси абсцисс, то отображаем карту леса симметрично относительно биссектрисы первого и третьего координатных углов, для этого меняем x на y и y на x. Делается это для того, чтобы не рассматривать отдельно случай проектирования на ось ординат, когда данный вектор направлен параллельно оси OX. Находим уравнения прямых, проходящих через центры окружностей, параллельно данному вектору и абсциссы точек пересечения этих прямых с осью ОХ. Например для окружности (x1,y1,r1). Уравнение прямой ax+by+c=0.a=-b₁;b=a₁; Найдем с. Так как точка (x₁,y₁) принадлежит прямой, то ее координаты обращают уравнение прямой в истинное числовое равенство. Отсюда с=-ax₁-by₁. На оси OY координата y=0, следовательно ax+c=0 и x=-c/a. то есть x=(ax₁+by₁)/a.

Тогда x₁₁=x-r₁/sin, x₂₁=x+r₁/ sin.

Для нахождения угла  используем тангенс. Если а1=0, то =/2, иначе tg =b₁/a₁

Если b₁/a₁>0, то =arctg b₁/a₁.,угол острый .Если b₁/a₁<0, то =+arctg b₁/a_1,,угол тупой.

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

Например для первых двух отрезков:

1)

x₁₁ x₂₁ x₁₂ x₂₂ отрезки не пересекаются x₂₁<x₁₂ в этом случае d= x₁₂- x₂₁

x₁₁ x₁₂ x₂₁ x₂₂ отрезки пересекаются x₂₁>=x_12, в этом случае d=0.

Выбираем наибольшее расстояние max между отрезками , умножаем его на sin и получаем ответ. Если max=0, то тропинку провести нельзя.

Рассмотрим несколько задач на применение формулы площади ориентированного треугольника.

Задача 50 Повороты

Дана незамкнутая простая ломаная с известными координатами вершин. Определить количество правых и левых поворотов при движении по ломаной от начала до конца.

С определением ломаной у участников олимпиад возникают трудности. И связано это вот с чем. В школьном курсе геометрии дается следующее определение ломаной.

Опр. Ломаной А₁А₂…A_n называется фигура, которая состоит из точек А1,А2,…An и соединяющих их отрезков. Ломаная называется простой, если она не имеет самопересечений. В определении ломаной ничего не говорится о том, что два соседних звена ломаной не могут лежать на одной прямой. То есть

Фигура A1 A2 A3 считается ломаной по школьному

определению. Но в школе такого вида ломаные не встречаются, и у учеников создается впечатление, что такого вида фигуры вовсе не ломаные, а отрезки.

М ы будем считать, что если два звена ломаной лежат на одной прямой, то поворота нет.

A₂ A₄ A₆

A₅

А₁ A₃ A₇

A₈

Используем формулу площади ориентированного треугольника. Если площадь треугольника А₁А₂А₃отрицательна, то поворот идет направо в точке А₂, если положительна, то налево, если равна нулю, то поворота нет. Если мы попытаемся изобразить нашу ломаную на экране, то надо помнить, что система координат экрана левая и все левые повороты станут правыми и наоборот.

Задача 51 Точка и треугольник

Дан треугольник АВС и точка М. Причем A(x1,y1), B(x2,y2),C(x3,y3), M(x0,y0). Выяснить принадлежит ли точка треугольнику.

B

B

М M

С

C

A C

A

Проведем две прямые AM и BM и найдем их уравнения. Выясним по одну или по разные стороны от прямой АM лежат точки В и С, и от прямой ВМ точки А и С. Если в обоих случаях по разные, то точка принадлежит треугольнику, если хотя бы в одном по одну , то не принадлежит. Но в отличии от предыдущей задачи придется изменить условие. Если S1*S2>0 то точки лежат по одну сторону от прямой, если S1*S2<=0, то по разные, то есть будем считать, что точки лежащие на границе полуплоскости ей не принадлежат.

. Задача 52 Выпуклость многоугольника

Дан многоугольник с координатами вершин перечисленных в порядке обхода по часовой или против часовой стрелки. Определить выпуклый он или нет.

Многоугольник представляет из себя замкнутую ломаную. Пройдем по этой ломаной начиная от первой вершины. Если все повороты происходят направо при обходе по часовой стрелке или налево при обходе против часовой стрелки, то многоугольник выпуклый, иначе нет. Считаем A_n+1.=A₁

Задача 53 Площадь произвольного многоугольника

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

y

A1=A5

A4 A2

A3

A3

O x

Введем фиктивную вершину А_n+1.

Положим А_n+1=А₁ Вычислим последовательно ориентированные площади треугольников OA₁A₂,OA₂A₃,OA₃A_4, OA₄A_5, сложим полученные площади и возьмем модуль полученного числа. Это и будет площадь данного многоугольника. Почему это так легко понять из чертежа. В качестве точки О можно взять любую точку плоскости, например вершину А₁ и результат будет тот же.

program smnogo;

const eps:real=1e-7; nmax=100;

tpoint=record определение типа точка (x,y)

x,y:real;

end;

var a:array[0..nmax] of :point;

res,s:real;

i,j,n:integer;

function streug(const A,B,C:tpoint):real; площадь ориентированного треугольника

begin

streug:=0.5*((C.Y-B.y)*(B.x-A.x)-(C.x-B.x)*(B.y-A.y));

end;

procedure init;

begin

assign(input,'input.txt'); reset(input);

read(n);

a[n+1].x:=a[1].x;

a[n+1].y:=a[1].y;

a[0].x:=0;

a[0].y:=0;

for i:=1 to n do read(a[i].x,a[i].y);

end;

procedure out;

begin

assign(output,'output.txt'); rewrite(output);

writeln(abs(s):0:3);

end;

procedure solve;

begin

s:=0;

for i:=1 to n do

s:=s+streug(a[0],a[i],a[i+1]);

end;

begin init; solve; out;end.

Задача 54 Деление отрезка в данном отношении

A(x1,y1 C(x,y) B(x2,y2)

Пусть вектор AC=k*CB.Если векторы связаны каким-то соотношением, то их координаты связаны таким же соотношением.

x-x1=k*(x2-x) отсюда x=(x1+k*x2)/(1+k)

y-y1=k*(y2-y) y=(y1+k*y2)/(1+k)

Е сли точка С середина отрезка АВ, то x=(x1+x2)/2

y=(y1+y2)/2

Задача 55 Разделить площадь данного треугольника АВС в отношении равном k

B Дано:AD/DB=k, то есть AD=k*DB

Треугольники ABD и BCD имеют

общую высоту BE.

A E D C

Следовательно

S_ABD=0.5*AD*BE

S_ABD=0.5*DC*BE

тогда S_ABD=k* S_ABD

И задача сводится к нахождению координат точки D.

Задача 56 Окружность и треугольник

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

Входные данные: в первой строке вводятся через пробел координаты центра окружности и ее радиус (X, Y, R). В последующих трех строках вводятся через пробел построчно координаты вершин треугольника. Все числа - целые.

Выходные данные: целое число-количество общих точек. Пример

Input.txt	Output.txt
0 0 4 0 0 0 50 50 0	2

В этой задаче надо аккуратно рассмотреть асе возможные случаи взаимного расположения данных фигур.

type real=extended;

const eps=1e-5;

var

k,n,res,x1,x2,x3,y1,y2,y3,a,b,c:integer;

x0,y0,d,x,y,u,v,q,r:real;

log1,log2:boolean;

procedure init;

var i:integer;

begin

assign(input,'input.txt');reset(input);

read(x1,y1,x2,y2,x3,y3); считываем данные

read(x0,y0,r);

close(input);

res:=0;

end;

procedure point2toline(x1,y1,x2,y2:integer;var a,b,c:integer); нахождение уравнения прямой

begin

a:=y2-y1;

b:=x1-x2;

c:=y1*x2-x1*y2;

end;

function rast2(x1,y1,x2,y2:real):real; расстояние между двумя точками

begin

rast2:=sqrt(sqr(x2-x1)+sqr(y2-y1));

end;

procedure find(x1,y1,x2,y2:integer);

begin

point2toline(x1,y1,x2,y2,a,b,c); находим уравнение прямой

if b=0 если прямая горизонтальна

then

begin

d:=r*r-sqr(c/a+x0);

if (d<=eps)and(d>=0)

then

begin

x:=-c/a;y:=y0;

if rast2(x1,y1,x,y)+rast2(x,y,x2,y2)-rast2(x1,y1,x2,y2)=0

then inc(res)

end

else if d>eps

then

begin

x:=-c/a;

y:=y0+sqrt(r*r-sqr(c/a+x0));

if rast2(x1,y1,x,y)+rast2(x,y,x2,y2)-rast2(x1,y1,x2,y2)=0

then inc(res);

y:=y0-sqrt(r*r-sqr(c/a+x0));

if rast2(x1,y1,x,y)+rast2(x,y,x2,y2)-rast2(x1,y1,x2,y2)=0

then inc(res)

end;

end

else

if b<>0

then

begin

u:=1+a*a/(b*b);

v:=2*a*y0/b+2*a*c/(b*b)-2*x0;

q:=x0*x0+c*c/(b*b)+2*c*y0/b-r*r+y0*y0;

d:=v*v-4*u*q;

if (d<=eps)and(d>=0)

then

begin

x:=-v/(2*u);

y:=-(a*x+c)/b;

if rast2(x1,y1,x,y)+rast2(x,y,x2,y2)-rast2(x1,y1,x2,y2)<=eps

then inc(res)

end

else

if d>eps

then

begin

x:=(-v+sqrt(d))/(2*u);

y:=-(a*x+c)/b;

if rast2(x1,y1,x,y)+rast2(x,y,x2,y2)-rast2(x1,y1,x2,y2)<=eps

then inc(res);

x:=(-v-sqrt(d))/(2*u);

y:=-(a*x+c)/b;

log1:=rast2(x1,y1,x,y)+rast2(x,y,x2,y2)-rast2(x1,y1,x2,y2)<=eps;

if rast2(x1,y1,x,y)+rast2(x,y,x2,y2)-rast2(x1,y1,x2,y2)<=eps

then inc(res)

end;

end;

end;

procedure versh; проходит ли окружность через вершины треугольника

begin

if ((x1-x0)*(x1-x0)+(y1-y0)*(y1-y0)-r*r)<=eps

then dec(res);

if ((x2-x0)*(x2-x0)+(y2-y0)*(y2-y0)-r*r)<=eps

then dec(res);

if abs((x3-x0)*(x3-x0)+(y3-y0)*(y3-y0)-r*r)<=eps

then dec(res);

end;

procedure out;

var i:integer;

begin

assign(output,'output.txt');

rewrite(output);

writeln(res);

close(output);

end;

begin

init;

find(x1,y1,x2,y2);

find(x1,y1,x3,y3);

find(x3,y3,x2,y2);

versh;

out;

end.

Задача 57 Коза на привязи

Есть ведь счастливые люди, которым иногда нечего делать. Лежат они на травке, мечтают или придумывают для себя какие-нибудь пустяковые задачки и с удовольствием их решают.

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

Входные данные:

в первой строке содержит одно вещественное число R – длину веревки (0<R<100000000)

Во второй строке два вещественных числа x₁,y₁-координаты левого нижнего угла прямоугольника

В третьей строке два вещественных числа x₂,y₂-координаты правого верхнего угла прямоугольника

Причем (-1000000<=x_i,y_i<=1000000 )

Выходные данные:

одно вещественное число – площадь огорода, объеденного козой.

Площадь вывести с тремя знаками после десятичной точки.

Пример

Input.txt	Output.txt
1.0000 -1.000 -1.000 3.000 3.000	3.142

На рисунке изображены все возможные случаи.

program koza;

type real=extended;

ar=array[1..2,1..4]of real;

const eps=0.5e-3;

var i,j,n,m,l,k:longint;

s1,s2,provs,prova1,prova2,prov,alf,x0,y0,s,r,x1,y1,xv,yv,xg,yg:real;

a:ar;

function realeq(const a,b:real):boolean;

begin

realeq:=abs(a-b)<=eps;

end;

function realmoreeq(const a,b:real):boolean;

begin

realmoreeq:=a-b>=eps;

end;

function realmore(const a,b:real):boolean;

begin

realmore:=a-b>eps;

end;

function reallesseq(const a,b:real):boolean;

begin

reallesseq:=b-a>=eps;

end;

function realless(const a,b:real):boolean;

begin

realless:=b-a>eps;

end;

function getangle(x,y:real):real;

var c:real;

begin

if realeq(y,0) then getangle:=0

else

begin

c:=x/r;

if realeq(c,0) then c:=Pi/2

else c:=arctan(sqrt(abs(1-sqr(c)))/c);

getangle:=c;

end;

end;

procedure Init;

var i,j:longint;

begin

Assign(input,'input.txt'); Reset(input);

read(r);

read(a[1,1],a[2,1]);

read(a[1,3],a[2,3]);

a[1,2]:=a[1,1];a[2,2]:=a[2,3];

a[1,4]:=a[1,3];a[2,4]:=a[2,1];

Close(input);

end;

procedure out;

begin

Assign(output,'output.txt'); Rewrite(output);

write(s:0:3);

Close(output);

end;

Procedure Solve;

begin

x0:=(a[1,1]+a[1,3])/2; находим координаты центра

y0:=(a[2,1]+a[2,3])/2;

for i:=1 to 4 do переносим центр в начало координат

begin

a[1,i]:=a[1,i]-x0;

a[2,i]:=a[2,i]-y0;

end;

x1:=a[1,3];

y1:=a[2,3];

if realmoreeq(r,sqrt(sqr(x1)+sqr(y1))) если прямоугольник внутри круга

then begin s:=4*x1*y1;out;halt(0) end; коза съест всю траву

if (reallesseq(r,x1))and(reallesseq(r,y1)) если круг внутри прямоугольника

then begin s:=pi*sqr(r);out;halt(0) end;

if realmore(r,y1)and reallesseq(r,x1) если круг пересекает верхнюю и

нижнюю стороны

then

begin

xg:=sqrt(sqr(r)-sqr(y1));

yg:=y1;

xv:=x1;

yv:=0;

end

else

if realmore(r,x1)and reallesseq(r,y1) если круг пересекает боковые стороны

then

begin

yv:=sqrt(sqr(r)-sqr(x1));

xv:=x1;

xg:=0;

yg:=y1;

end

else

begin

xg:=sqrt(sqr(r)-sqr(y1));

yg:=y1;

yv:=sqrt(sqr(r)-sqr(x1));

xv:=x1;

end;

alf:=abs(getangle(xg,yg)-getangle(xv,yv)); вычисляем площадь сегмента

s1:=y1*xg/2; s2:=x1*yv/2;

s:=2*(y1*xg+x1*yv+sqr(r)*alf);

end;

begin Init; Solve; out; end.

Задача 58 Анамейтронная звезда

На небе всем известной планеты Анаметроники можно увидеть немало звезд. Но у анаметрян всё не как у людей! Все звезды у них плоские и представляют собой геометрические фигуры, называемые анамейтронными звездами.

Анамейтронная звезда строится следующим способом:

Строится окружность единичного радиуса;

На окружности равномерно распределяются N точек, где N – порядок звезды;

Для каждой точки строится окружность единичного радиуса с центром в этой точке;

Области наложения двух и более окружностей закрашиваются.

З акрашенная часть фигуры и будет называться N-конечной анамейтронной звездой.

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

Формат входного файла

Файл содержит единственное натуральное число N (2<N<=1000)

Формат выходного файла

Файл должен содержать единственное действительное число S с точностью до пяти знаков после десятичной точки – площадь N-конечной анамейтронной звезды.

Примеры

Input.txt	Output.txt
4	2.28318

Program zvezda;

function asin(alpha:real):real; нахождение угла

function asin(alpha:real):real; нахождение угла

var a:real;

begin

a:=alpha/sqrt(1-alpha*alpha);

asin:=arctan(a);

end;

function MSquare(var d,r:real):real; нахождение площади сегмента

var a,alpha,s:real;

begin

a:=sqrt(r*r-0.25*d*d);

alpha:=2*asin(a/r);

if d>=2*r then s:=0 else s:=alpha*r*r-a*d;

MSquare:=s;

end;

var n:integer;

r,d,d1,d2,s:real;

s1:string;

begin

Assign(input,'input.txt'); reset(input);

Assign(output,'output.txt'); rewrite(output);

r:=1;

read(n);

d:=sqrt(2.0)*r*sqrt(1-cos(2*Pi/n));

d2:=sqrt(2.0)*r*sqrt(1-cos(4*Pi/n));

S:=n*(MSquare(d,r)-MSquare(d2,r));

if n=3 then s:=n*MSquare(d,r);

write(S:0:5);

close(output);

end.

Задача 59 Кролик и бобер

Два друга- кролик и бобер жили неподалеку друг от друга. Кролик вырыл норку в степи, а бобер обитал в норке на берегу озера, которое имело форму выпуклого многоугольника. Друзья часто ходили друг к другу в гости и, чтобы не терять лишнего времени, нашли кратчайшую дорогу между норками (друзья отличались умом и сообразительностью).

Напишите программу, определяющую минимально возможную длину пути между норками.