Формули обчислювальної геометрії

Добавил(а) Administrator

07.12.11 12:54

Формули обчислювальної геометрії

Визначення площі довільного многокутника
За заданими координатами вершин многокутника визначити його площу.
Для обчислення площі можна використати формулу:

Перевірка многокутника на опуклість
{ Зчитування координат вершин многокутника}
assign(f,'input.txt');
reset(f);
readln(f,n);
for i:=1 to n do readln(f,x[i],y[i]);
close(f);
{Визначення координат векторів}
x[n+1]:=x[1];
y[n+1]:=y[1];
for i:=1 to n do begin
a[i]:=x[i+1]-x[i];
b[i]:=y[i+1]-y[i];
end;
{Підрахунок кількості додатних добутків}
a[n+1]:=a[1];
b[n+1]:=b[1];
k:=0;
for i:=1 to n do
if a[i]*b[i+1]-a[i+1]*b[i]>=0 then k:=k+1;
{Виведення результату}
assign(f,'output.txt');
rewrite(f);
if (k=n)or(k=0) then writeln(f,'yes') else writeln(f,'no');
close(f);

Належність точки прямій

(x-x1)/(x2-x1)=(y-y1)/(y2-y1)
(x-x1)* (y2-y1) =(y-y1)* (x2-x1)

p:=false;
if (x-x1)* (y2-y1) -(y-y1)* (x2-x1)=0 then p:=true;

Перетин прямих

(x-x1)/(x2-x1)=(y-y1)/(y2-y1)
(x-x1)* (y2-y1) =(y-y1)* (x2-x1)

(x-x3)/(x4-x3)=(y-y3)/(y4-y3)
(x-x3)* (y4-y3) =(y-y3)* (x4-x3)

1)
x=(y-y1)*(x2-x1)/(y2-y1)+x1
(x-x3)* (y4-y3) =(y-y3)* (x4-x3)

((y-y1)*(x2-x1)-(x3-x1)*(y2-y1))*(y4-y3)=(y-y3)*(x4-x3)*(y2-y1)
(y-y1)*(x2-x1)*(y4-y3)-(y-y3)*(x4-x3)*(y2-y1)=(x3-x1)*(y2-y1)*(y4-y3)
y((x2-x1)*(y4-y3)-(x4-x3)*(y2-y1))= (x3-x1)*(y2-y1)*(y4-y3)+y1*(x2-x1)*(y4-y3)-y3*(x4-x3)*(y2-y1)

y=((x3-x1)*(y2-y1)*(y4-y3)+y1*(x2-x1)*(y4-y3)-y3*(x4-x3)*(y2-y1))/ ((x2-x1)*(y4-y3)-(x4-x3)*(y2-y1))

2)
y=(x-x1)*(y2-y1)/(x2-x1)+y1
(y-y3)* (x4-x3) =(x-x3)* (y4-y3)

((x-x1)*(y2-y1)-(y3-y1)*(x2-x1))*(x4-x3)=(x-x3)*(y4-y3)*(x2-x1)
(x-x1)*(y2-y1)*(x4-x3)-(x-x3)*(y4-y3)*(x2-x1)=(y3-y1)*(x2-x1)*(x4-x3)
x((y2-y1)*(x4-x3)-(y4-y3)*(x2-x1))= (y3-y1)*(x2-x1)*(x4-x3)+x1*(y2-y1)*(x4-x3)-x3*(y4-y3)*(x2-x1)

x=((y3-y1)*(x2-x1)*(x4-x3)+x1*(y2-y1)*(x4-x3)-x3*(y4-y3)*(x2-x1))/ ((y2-y1)*(x4-x3)-(y4-y3)*(x2-x1))
Перетин відрізків:
if (x1<=x2)and(x>=x1)and(x<=x2) then p:=true;
if (x2<=x1)and(x>=x2)and(x<=x1) then p:=true;
Перетин відрізків
var x1,y1,x2,y2,x3,y3,x4,y4,x,y:real;
p:boolean;
begin
clrscr;
writeln('x1,y1');
readln(x1,y1);
writeln('x2,y2');
readln(x2,y2);
writeln('x3,y3');
readln(x3,y3);
writeln('x4,y4');
readln(x4,y4);
p:=false;
if (((x2-x1)*(y4-y3)-(x4-x3)*(y2-y1))<>0) and (y2-y1<>0) then
begin
y:=((x3-x1)*(y2-y1)*(y4-y3)+y1*(x2-x1)*(y4-y3)-y3*(x4-x3)*(y2-y1))/((x2-x1)*(y4-y3)-(x4-x3)*(y2-y1));
x:=(y-y1)*(x2-x1)/(y2-y1)+x1;
p:=true;
end;

{if p then writeln(x:2:2,' ',y:2:2);}

p:=false;
if (((y2-y1)*(x4-x3)-(y4-y3)*(x2-x1))<>0)and (x2-x1<>0)then
begin
x:=((y3-y1)*(x2-x1)*(x4-x3)+x1*(y2-y1)*(x4-x3)-x3*(y4-y3)*(x2-x1))/ ((y2-y1)*(x4-x3)-(y4-y3)*(x2-x1));
y:=(x-x1)*(y2-y1)/(x2-x1)+y1;
p:=true;
end;

if p then
begin
p:=false;
if (x1<=x2)and(x>=x1)and(x<=x2) then p:=true;
if (x2<=x1)and(x>=x2)and(x<=x1) then p:=true;
end;

if p then writeln(x:2:2,' ',y:2:2);
end.

Задача 1. Рух автомобіля
Маршрут руху автомобіля заданий у вигляді координат вершин ламаної. Необхідно визначити кількість лівих поворотів. Автомобіль починає рух першої вершини ламаної.

Задача 2. Едемський сад
Едемський сад складається з N фруктових дерев, розміщення яких задано координатами (Xi,Yi), а їх врожайності, відповідно, дорівнюють Ui, i=1,2,...,N. Садівник обгородив сад огорожею мінімальної довжини. Розробити програму, яка виводить на екран план Едемського саду, на якому ілюструється взаємне розміщення огорожі і дерев. При цьому:
1. Забезпечити можливість введення початкових даних як з клавіатури, так і з файлу EDEM.GOD, і відображати їх на дисплеї у вигляді плану Едемського саду (врахувати, що перший запис файлу EDEM.GOD вміщує значення N, а в кожному з наступних N записів вміщуються по три числа - Xi, Yi і Ui, де 1? i ? N, N ? 20; числа в кожному записі розділені пропусками. (5 балів).
2. Забезпечити можливість діалогу редагування початкових даних з синхронним відображенням результатів редагування на плані Едемського саду. (5 балів).
3. Обчислювати і виводити на дисплей врожайність всього саду. (5 балів).
4. Обчислювати і виводити на дисплей максимальну відстань між деревами саду. (5 балів).
5. Обчислювати і виводити на дисплей мінімальну відстань між сусідніми деревами саду. (5 балів).
6. Визначати кількість рогів в найкоротшій огорожі. (12 балів).
7. Обчислювати і виводити на дисплей периметр огорожі саду. (10 балів).
8. Обчислювати і виводити на дисплей площу обгородженого саду. (10 балів).
9. Автоматично наносити на план саду найкоротший маршрут, додержуючись якого, можна обійти всі дерева і повернутися до місця старту, обчислювати відстань за цим маршрутом. (12 балів).
10. Динамічно відображати на плані обхід Едемського саду садівником вздовж знайденого найкоротшого маршруту. (10 балів)

Главное меню

Статистика

Пользователей : 261
Статей : 225
Просмотрено статей : 115279

Вход/Регистрация

Нет

Сайт підготовки до олімпіади з інформатики

Главное меню

Статистика

Вход/Регистрация