INFOMAN брой 5
{
Условие на Задача 2:
Даден е квадрат в равнината, зададен с координатите на два свои
противоположни върха и кръг зададен с координатите на центъра си и дължината
на радиуса си.
Напишете програма, която намира лицето на сечението на двете фигури.
Входният файл INPUT2.TXT съдържа точно 3 реда. В първите два са записани
координатите на два срещуположни върха на квадрата. На третия ред са записани
3 числа: координатити на центъра на кръга и дължината на радиуса му (разделени
с интервал).
В изходния файл OUTPUT2.TXT запишете точно едно число - лицето на сечението
на двете фигури (с точност две цифри след дасетичната точка).
Примерен входен файл: Примерен изходен файл:
INPUT2.TXT OUTPUT2.TXT
0 5.0 46.64
10.00 -5
3.0 1 4.000
Решение:
}
{$A+,B-,D+,E+,F-,G+,I+,L+,N-,O-,P-,Q+,R+,S+,T-,V-,X+,Y+}
{$M 65000,0,655360}
const epsilon=0.01; {за да работи за по големи размери на фигурите или с
по-голяма точност, намалете константата}
type tcoord=real; {ако по време на изпълнение на програмата ви излезе грешка}
tvalue=real; {Invalid floating point operation, спрете поддръжката на}
tangle=real; {8087/80287, защото компилатора не генерира добър код за тях}
tpoint=record
x,y:tcoord;
end;
tpolarpoint=record
a:tangle;
d:tvalue;
end;
var quad1,quad2:tpoint;
center:tpoint;
radius:tvalue;
result:tvalue;
procedure inp; {т.1 Вход}
var f:text;
begin
assign(f,'input2.txt'); {това е без коментар}
reset(f);
readln(f,quad1.x,quad1.y); {координатите на първата точка}
readln(f,quad2.x,quad2.y); {координатите на втората точка}
readln(f,center.x,center.y,radius); {центъра на кръга и радиуса му}
close(f); {за малко да забравя това}
end;
procedure wrout;{т.5 Изход}
var f:text;
begin
assign(f,'output2.txt');
rewrite(f);
writeln(f,result:0:2);
close(f);
end;
procedure centerit; {т.2 Центриране}
begin {центрира сцената по първата точка от квадрата}
quad2.x:=quad2.x-quad1.x;
quad2.y:=quad2.y-quad1.y;
center.x:=center.x-quad1.x;
center.y:=center.y-quad1.y;
quad1.x:=0;
quad1.y:=0;
end;
procedure rotate; {т.3 Завъртане на сцената}
{завърта сцената така че втората точка от квадрата да се намира на 1h30'(pi/4)}
var q2p,cp:tpolarpoint;
procedure topolar(p:tpoint;var result:tpolarpoint);
{т.3.1 Превръщане в полярни координати}
begin {когато връщате резултат по този начин, никога не забравяйте var директивата}
if p.x=0 then
result.a:=pi/2
else
result.a:=arctan(p.y/p.x);{работи в областта (-pi/2;pi/2)(12h-6h)}
if (p.x<0) or {за това ако е pi/2(12h) го правим ръчно}
((p.x=0) and (p.y<0)) then
result.a:=result.a+pi; {а ако е в другата половина на обобщения ъгъл [6h-12h) му прибавяме pi}
result.d:=sqrt(sqr(p.x)+sqr(p.y));
end;
procedure frompolar(pp:tpolarpoint;var result:tpoint);
{т.3.3 Превръщане от полярни координати}
var thesin,thecos:tvalue;
begin
result.x:=cos(pp.a)*pp.d;{това е твърде лесно за да го обяснявам}
result.y:=sin(pp.a)*pp.d;
end;
begin
topolar(quad2,q2p); {т.3.1 обръща координатите в полярни}
topolar(center,cp);
cp.a:=cp.a+((pi/4)-q2p.a); {т.3.2 пипва малко ъгъла}
q2p.a:=pi/4;
frompolar(q2p,quad2); {т.3.3 и ги обръща обратно}
frompolar(cp,center)
end;
function pointinside(x,y:tcoord):boolean;
begin
pointinside:=(sqr(x-center.x)+sqr(y-center.y)<=sqr(radius));
{този израз не трябва да ви учудва..., ако е така разберете как работи.}
end;
function pointoutside(x,y:tcoord):boolean;
begin
pointoutside:=(sqr(x-center.x)+sqr(y-center.y)>=sqr(radius));
end;
function quadinside(x1,y1,x2,y2:tcoord):boolean;
{проверява дали квадрадрата зададен с двата си срещуположни ъгъла
е изцяло вътре в кръга}
begin
quadinside:=pointinside(x1,y1) and pointinside(x2,y2) and
pointinside(x1,y2) and pointinside(x2,y1);
end;
function quadoutside(x1,y1,x2,y2:tcoord):boolean;
{проверява дали квадрата е изцяло извън кръга}
begin
if not pointoutside(x1,y1) or
not pointoutside(x1,y2) or
not pointoutside(x2,y1) or
not pointoutside(x2,y2) then begin
quadoutside:=false;
exit;
end; {и четирите точки трябва да са извън кръга, но това не е достатъчно условие}
if (center.y<=y1-radius) or
(center.y>=y2+radius) or
(center.x<=x1-radius) or
(center.x>=x2+radius) then begin
quadoutside:=true;
exit;
end; {когато е очевидно отвън, но има и още случаи.....}
if (center.y<y1) and (center.x<x1) or
(center.y<y1) and (center.x>x2) or
(center.y>y2) and (center.x<x1) or
(center.y>y2) and (center.x>x2) then begin
quadoutside:=true;
exit;
end;{е, за този случай доста си блъсках главата...,
надявам се да е имало защо :) }
quadoutside:=false;
end;
function microinside(x1,y1,x2,y2:tcoord):boolean;
{проверява за миниатюрните квадратчета дали са вътре в кръга}
{като за тях се смята че са вътре ако центъра им е вътре}
begin
microinside:=sqr((x1+x2)/2-center.x)+sqr((y1+y2)/2-center.y)<sqr(radius);
end;
function rec(x1,y1,x2,y2:tcoord):tvalue; {т.4 виж описанието за повече подробности}
var cx,cy:tcoord;
begin
if abs(x1-x2)<epsilon then begin {ако сме стигнали до състояние на }
if microinside(x1,y1,x2,y2) then rec:=sqr(x2-x1) {миниатюрно квадратче}
else rec:=0; {гледаме дали е вътре и ако е }
exit;{лицето на сечението е лицето на квадратчето}
end;
if quadinside(x1,y1,x2,y2) then begin {ако квадрата е изцяло вътре}
rec:=sqr(x2-x1); {тогава лицето на сечението е лицето на квадрата}
exit;
end;
if quadoutside(x1,y1,x2,y2) then begin
rec:=0; {ако е изцяло отвън, тогава лицето на сечението е 0}
exit;
end;
cx:=(x1+x2)/2; {ако не е нито отвън нито вътре тогава го цепим на 4 и }
cy:=(y1+y2)/2; {лицето на сечението е сбора от лицата на 4-те сечения}
rec:=rec(x1,y1,cx,cy)+rec(cx,y1,x2,cy)+rec(x1,cy,cx,y2)+rec(cx,cy,x2,y2);
end;
begin
inp; {т.1 Вход}
centerit; {т.2 Центриране}
rotate; {т.3 Завъртане}
result:=rec(quad1.x,quad1.y,quad2.x,quad2.y); {т.4 Същинска работа}
wrout; {т.5 Изписване на резултата}
end.
Входен файл input2.txt
0.0 0.0
1.0 1.0
1.0 1.0 0.5
Изходен файл output2.txt
0.20
Описание на решението.
1. Вход:
това на всички е ясно (надявам се :)
2. Центриране:
за целта на задачата и за да си олесним работата, ще центрираме сцената по
една точка. В случая аз избрах първата точка на квадрата.
3. Завъртане:
пак за ди олесним работата нататък...., метода който използвам в случая е с
преобразуване в полярни координати и обратно. Базира се на идеята че ако
разгледаме разстоянието на всяка точка до центъра на завъртане и ъгъла, на
който се намира спрямо 3 часа, можем много лесно да я завъртим, като само
променим този ъгъл. Например точка с координати 1,1 има полярни координати
ъгъл:45ø, разстояние:û2. (1,-1) ще има:ъгъл:-45ø, разстояние:û2
3.1. Преобразуване в полярни координати:
т.к. Математиката не ни предоставя функция която да ни върне ъгъл в целия
диапазон, се налага да си свършим работата по информатически. Разбиваме
диапазона на 2 части и .....
3.2. Самото завъртане:
Тук само променяме ъгъла на точките, които завъртаме, като го правим така,
че втората точка на квадрата да се намира на ъгъл 45ø, с целта квадрата да
стане в края на краищата "изправен", т.е. страните му да са успоредни на
координатните оси.
3.3. Преобразуване обратно в познатата ни система от координати.
Тук работата е доста по лесна от 3.1 т.к си има готови функции.
4. Същинска работа.
След като подготвихме входните данни за обработка е време да направим и
самата обработка.
Ще пресметнем лицето по метода разделяй и владей.
1.Ако квадрата няма нищо общо с кръга: лицето е нула.
2.Ако квадрата е изцяло вътре: лицето е лицето на квадрата.
3.Ако квадрата не е нито вътре нито вън, т.е. е някъде по средата: лицето на
сечението е сбора на лицата на сеченията на 4-те части на квадрата с кръга.
4.И разбира се не можем да си позволим да разделяме квадрата на 4 вечно.
Просто не разполагаме с толкова умена машина. :)
Така че ни се налага да заложим някакво приближение за много малките
квадратчета, които ще се получат.
В това решение аз съм казал че ако центъра на едно малко квадратче е вътре в
кръга то и цялото се смята че е вътре и обратно. Това е доста по-добро
приближение от идеята че ако 4-те върха са вътре то е вътре, защото
натрупаната грешка с всяко квадратче е значително по-малка, а оттам и
крайния резултат по-точен
5. Изход
Не знам просто какво бих могъл да кажа за изхода.