Два прожектори трикутної форми утворюють на стіні дві плями, одну - блакитного, а другу - жовтого кольору. Визначити площу плями зеленого кольору, яка утвориться при накладанні двох плям та форму (кількість вершин) зеленої плями.
Вхідні дані
У першому рядку містяться координати однієї плями: x[11], y[11], x[12], y[12], x[13], y[13], а в другому рядку – такі ж координати вершин іншої плями x[21], y[21], x[22], y[22], x[23], y[23]. Відомо, що -100 ≤ x[i], y[i] ≤ 100
Вихідні дані
Вивести в єдиному рядку 2 числа: кількість вершин зеленої плями і, через пропуск, її площу (з двома знаками після коми).
Вхідні дані
2 2 2 6 8 4 5 4 11 6 11 2
Вихідні дані
4 1.50
Зрозуміло, що пляма зеленого кольору матиме не більше 6 вершин, якщо вона взагалі існує. Кожна з цих вершин - точка перетину сторін однієї плями зі сторонами іншої (якщо точка є внутрішньою точкою сторін, що перетинаються) або вершина однієї з плям, яка належить іншій.
program zp;
var dot, newdot, dotm:array[1..12] of record xx,yy:real end;
pass:set of byte;
flWork:boolean;
f:text;
i,i1,i2,i3,i4,n,pos:integer;
d,a1,a2,b1,b2:real;
{повертає координати точки перетину двох відрізків, якщо вони перетинаються}
function XLineLine(x11,y11,x12,y12,x21,y21,x22,y22:real; var x,y:real):boolean;
{перевірка належності точки прямокутнику}
function InBox2d(xk,yk,x1,y1,x2,y2:real):boolean;
var xl,yl,xh,yh:real;
begin
if x1<x2 then
begin
xl:=x1; xh:=x2
end
else
begin
xl:=x2; xh:=x1
end;
if y1<y2 then
begin
yl:=y1; yh:=y2
end
else
begin
yl:=y2; yh:=y1
end;
InBox2d:=((xk>=xl) and(xk<=xh) and(yk>=yl) and(yk<=yh));
end;
begin
XLineLine:=false;
a1:=x12-x11; a2:=y12-y11;
b1:=x22-x21; b2:=y22-y21;
d:=a1*b2-a2*b1;
if d=0 then exit;
if abs(a2)>abs(a1) then
begin
y:=(a1*b2*y11-a2*b2*(x11-x21)-a2*b1*y21)/d;
x:=a1/a2*(y-y11)+x11
end
else
begin
x:=-(a2*b1*x11-a1*b1*(y11-y21)-a1*b2*x21)/d;
y:=a2/a1*(x-x11)+y11
end;
XLineLine:=(InBox2d(x,y,x11,y11,x12,y12)) and (InBox2d(x,y,x21,y21,x22,y22));
end;
{обчислення площі многокутника}
function SNcut(col:integer):real;
var i,i1:integer; s:real;
begin
s:=0;
for i:=1 to col do
begin
if i<col then i1:=i+1 else i1:=1;
s:=s+dotm[i].xx*dotm[i1].xx*dotm[i].yy
end;
Sncut:=abs(s/2);
end;
{перевірка належності точки трикутнику}
function In3cut(x,y,x1,y1,x2,y2,x3,y3:real):boolean;
var s,s1,s2,s3:real;
begin
with dotm[1] do
begin
xx:=x; yy:=y
end;
with dotm[2] do
begin
xx:=x1; yy:=y1
end;
with dotm[3] do
begin
xx:=x2; yy:=y2
end;
s1:=sncut(3);
with dotm[2] do
begin
xx:=x2; yy:=y2
end;
with dotm[3] do
begin
xx:=x3; yy:=y3
end;
s2:=sncut(3);
with dotm[2] do
begin
xx:=x1; yy:=y1
end;
with dotm [3] do
begin
xx:=x3; yy:=y3
end;
s3:=sncut(3);
with dotm[1] do
begin
xx:=x2; yy:=y2
end;
s:=sncut(3);
in3cut:=(s=s1+s2+s3);
end;
{головна програма}
begin
assign(f,'input.txt'); reset(f);
for i:=1 to 6 do
read(f, dot[i].xx, dot[i].yy);
close(f);
{точки першого трикутника всередині другого}
pos:=0;
for i:=1 to 3 do with dot[i] do
if in3cut(xx,yy,dot[4].xx,dot[4].yy,dot[5].xx,dot[5].yy,dot[6].xx,dot[6].yy) then
begin
inc(pos);
newdot[pos].xx:=xx;
newdot[pos].yy:=yy
end;
{точки другого трикутника всередині першого}
for i:=4 to 6 do with dot[i] do
if in3cut(xx,yy,dot[1].xx,dot[1].yy,dot[2].xx,dot[2].yy,dot[3].xx,dot[3].yy) then
begin
inc(pos);
newdot[pos].xx:=xx;
newdot[pos].yy:=yy
end;
{точки перетину сторін трикутників}
for i:=1 to 3 do
begin
if i<3 then i1:=i+1;
for i2:=1 to 3 do
begin
if i2<3 then i3:=i2+1 else i3:=1;
with newdot[pos+1] do
if xlineline(dot[i].xx, dot[i].yy,dot[i1].xx,dot[i1].yy,dot[3+i2].xx,dot[3+i2].yy,dot[3+i3].xx,
dot[3+i3].yy,xx,yy) then inc(pos);
end;
end;
{видаляємо точки, що повторюються}
i:=0;
repeat
inc(i);
repeat
n:=0;
for i1:=i+1 to pos do
if(newdot[i].xx=newdot[i1].xx) and (newdot[i].yy=newdot[i1].yy) then n:=i1;
if n<>0 then
begin
for i1:=n to pos-1 do newdot[i1]:=newdot[i1+1];
dec(pos);
end;
until n=0;
until i>=pos;
if pos>=3 then
begin
{визначаємо порядок обходу вершин многокутника}
pass:=[1]; dotm[1]:=newdot[1]; n:=1;
repeat
flWork:=true;
with dotm[n] do
for i:=1 to pos do if (not(i in pass))and(flWork) then
begin
a1:=newdot[i].xx-xx;
a2:=newdot[i].yy-yy;
i3:=0; i4:=0;
for i1:=1 to pos do
begin
d:=(newdot[i1].xx-xx)*a2-(newdot[i1].yy-yy)*a1;
if d<-0.000000001 then inc(i3);
if d>0.000000001 then inc(i4);
end;
if not((i3>0) and (i4>0)) then
begin
inc(n); pass:=pass+[i];
dotm[n]:=newdot[i]; flWork:=false
end;
end;
until n=pos;
d:=SNcut(pos);
end
else d:=0;
assign(f,'output.txt'); rewrite(f);
writeln(f,pos);
writeln(f,d:1:2);
close(f);
end.
Немає коментарів:
Дописати коментар