{
Author:wzx961008
Problem:sgu 345-Revolution
Verdict:Accepted
Language:PASCAL
Run Time:0.765s
Submission Date:26.08.11 08:25
}
{$MODE Delphi}
uses math;
const error=1e-8; maxn=50000; oo=1e10;
type point=record x,y:extended; end;
var pt,convex:array[1..maxn+1]of point;
sum:array[1..maxn+1]of extended;
fs:array[1..maxn*2+2]of point;
n,m,top:longint;
s:extended;
origin:point;
procedure swap(var p1,p2:point);
var t:point;
begin
t:=p1; p1:=p2; p2:=t;
end;
function cross(p11,p12,p21,p22:point):extended;
var x1,y1,x2,y2:extended;
begin
x1:=p12.x-p11.x;
y1:=p12.y-p11.y;
x2:=p22.x-p21.x;
y2:=p22.y-p21.y;
cross:=x1*y2-x2*y1;
end;
function dist(p1,p2:point):extended;
begin
dist:=sqrt(sqr(p1.x-p2.x)+sqr(p1.y-p2.y));
end;
procedure qsort_polar_angle(l,r:longint);
var i,j:longint;
m:point;
crs1,crs2,dstm:extended;
begin
i:=l; j:=r; m:=pt[l+random(r-l)];
repeat
dstm:=dist(pt[1],m);
repeat
crs1:=cross(pt[1],m,pt[1],pt[i]);
if not((crs1<-error)or((abs(crs1)<error)and(dstm>dist(pt[1],pt[i])))) then break;
inc(i);
until false;
repeat
crs2:=cross(pt[1],pt[j],pt[1],m);
if not((crs2<-error)or((abs(crs2)<error)and(dist(pt[1],pt[j])>dstm))) then break;
dec(j);
until false;
if i<=j then begin
swap(pt[i],pt[j]);
inc(i); dec(j);
end;
until i>j;
if l<j then qsort_polar_angle(l,j);
if i<r then qsort_polar_angle(i,r);
end;
procedure get_point;
var i:longint;
begin
readln(n);
for i:=1 to n do begin
readln(pt[i].x,pt[i].y);
if (pt[i].y<pt[1].y)or((abs(pt[i].y-pt[1].y)<error)and(pt[i].x<pt[1].x)) then swap(pt[1],pt[i]);
end;
end;
procedure get_convex;
var p,i:longint;
begin
for i:=1 to n do begin
inc(top); convex[top]:=pt[i];
if top>2 then begin
p:=top-1;
while (p>1)and(sign(cross(convex[p-1],convex[p],convex[p],convex[top]))<=0) do dec(p);
top:=p+1; convex[top]:=pt[i];
end;
end;
end;
function qd(p:point):longint;
begin
if (p.x>0)and(p.y>=0) then begin qd:=1; exit; end;
if (p.x<=0)and(p.y>0) then begin qd:=2; exit; end;
if (p.x<0)and(p.y<=0) then begin qd:=3; exit; end;
if (p.x>=0)and(p.y<0) then begin qd:=4; exit; end;
end;
function smler_pa(p11,p12,p21,p22:point):boolean;
var vc1,vc2:point;
qd1,qd2:longint;
begin
vc1.x:=p12.x-p11.x; vc1.y:=p12.y-p11.y;
vc2.x:=p22.x-p21.x; vc2.y:=p22.y-p21.y;
qd1:=qd(vc1); qd2:=qd(vc2);
if qd1<>qd2 then begin smler_pa:=qd1<qd2; exit; end;
smler_pa:=cross(p11,p12,p21,p22)>=0;
end;
procedure init;
var i:longint;
begin
get_point;
randomize;
qsort_polar_angle(2,n);
get_convex;
for i:=1 to top do begin
fs[i]:=convex[i];
fs[i+top]:=convex[i];
end;
sum[1]:=0;
for i:=2 to top do sum[i]:=sum[i-1]+cross(origin,convex[i-1],origin,convex[i]);
s:=sum[top]+cross(origin,convex[top],origin,convex[1]);
end;
function itst(p1,p2:point; a,b,c:extended; var ip:point):boolean;
var aa,bb,cc,tmp:extended;
begin
itst:=false;
if sign((a*p1.x+b*p1.y+c)*(a*p2.x+b*p2.y+c))<=0 then begin
itst:=true;
aa:=p1.y-p2.y; bb:=p2.x-p1.x; cc:=p1.x*p2.y-p2.x*p1.y;
tmp:=bb*a-b*aa; if sign(tmp)=0 then begin itst:=false; exit; end;
ip.x:=(b*cc-c*bb)/tmp;
ip.y:=(c*aa-a*cc)/tmp;
end;
end;
procedure main;
var i,fp1n,fp2n,cp1n,cp2n,i1s1,i1s2,i2s1,i2s2,tmp:longint;
p1,p2,ip,ip1,ip2:point;
a,b,c,s1:extended;
b1,b2,bb:boolean;
function next(x:longint):longint;
begin
if x=top then next:=1 else next:=x+1;
end;
function last(x:longint):longint;
begin
if x=1 then last:=top else last:=x-1;
end;
function check(p1,p2:point):boolean;
begin
check:=(abs(p1.x-p2.x)<error)and(abs(p1.y-p2.y)<error);
end;
function binary_search(p1,p2:point):longint;
var l,r,m:longint;
b1,b2:boolean;
vec:point;
begin
vec.x:=p2.x-p1.x; vec.y:=p2.y-p1.y;
if (cross(origin,vec,convex[top],convex[1])<=0)and(cross(origin,vec,convex[1],convex[2])>=0) then begin binary_search:=1; exit; end;
if (cross(origin,vec,convex[top-1],convex[top])<=0)and(cross(origin,vec,convex[top],convex[1])>=0) then begin binary_search:=top; exit; end;
l:=1; r:=top;
while true do begin
m:=(l+r) shr 1;
b1:=smler_pa(convex[m-1],convex[m],origin,vec);
b2:=smler_pa(origin,vec,convex[m],convex[m+1]);
if (b1)and(b2) then begin binary_search:=m; exit; end;
if (b1)and(not(b2)) then l:=m;
if (not(b1))and(b2) then r:=m;
end;
end;
function trinary_search(l,r:longint):longint;
var ll,rr,t1,t2,t,ret:longint;
fd1,fd2,fd3,min:extended;
begin
ll:=l; rr:=r;
if r<l then rr:=rr+top;
while true do begin
t:=(rr-ll) div 3; t1:=ll+t; t2:=rr-t;
fd1:=abs(a*fs[t1].x+b*fs[t1].y+c);
fd2:=abs(a*fs[t2].x+b*fs[t2].y+c);
if rr-ll<=2 then begin
min:=oo;
if rr-ll=2 then begin
fd3:=abs(a*fs[ll+1].x+b*fs[ll+1].y+c);
if fd3<min then begin
min:=fd3; ret:=ll+1;
end;
end;
if fd1<min then begin
min:=fd1; ret:=ll;
end;
if fd2<min then begin
min:=fd2; ret:=rr;
end;
trinary_search:=ret; exit;
end;
if fd1<fd2 then rr:=t2 else ll:=t1;
end;
end;
begin
readln(m);
for i:=1 to m do begin
readln(p1.x,p1.y,p2.x,p2.y);
a:=p1.y-p2.y; b:=p2.x-p1.x; c:=p1.x*p2.y-p2.x*p1.y;
fp1n:=binary_search(p1,p2);
fp2n:=binary_search(p2,p1);
cp1n:=trinary_search(fp1n,fp2n); if cp1n>top then cp1n:=cp1n-top;
cp2n:=trinary_search(fp2n,fp1n); if cp2n>top then cp2n:=cp2n-top;
b1:=true; b2:=true;
if itst(convex[last(cp1n)],convex[cp1n],a,b,c,ip) then begin
ip1:=ip; b1:=false; i1s1:=last(cp1n); i1s2:=cp1n;
end;
if itst(convex[cp1n],convex[next(cp1n)],a,b,c,ip) then begin
if b1 then begin ip1:=ip; b1:=false; i1s1:=cp1n; i1s2:=next(cp1n); end;
if not(check(ip1,ip))and(not(b1)) then begin
ip2:=ip; b2:=false; i2s1:=cp1n; i2s2:=next(cp1n);
end;
end;
if itst(convex[last(cp2n)],convex[cp2n],a,b,c,ip) then begin
if b1 then begin ip1:=ip; b1:=false; i1s1:=last(cp2n); i1s2:=cp2n; end;
if not(check(ip1,ip))and(not(b1)) then begin
ip2:=ip; b2:=false; i2s1:=last(cp2n); i2s2:=cp2n;
end;
end;
if itst(convex[cp2n],convex[next(cp2n)],a,b,c,ip) then begin
if b1 then begin ip1:=ip; b1:=false; i1s1:=cp2n; i1s2:=next(cp2n); end;
if not(check(ip1,ip))and(not(b1)) then begin
ip2:=ip; b2:=false; i2s1:=cp2n; i2s2:=next(cp2n);
end;
end;
if (b1)or(b2) then begin writeln('0.000000'); continue; end;
if i1s1>i1s2 then begin tmp:=i1s1; i1s1:=i1s2; i1s2:=tmp; end;
if i2s1>i2s2 then begin tmp:=i2s1; i2s1:=i2s2; i2s2:=tmp; end;
bb:=true;
if ((i1s1=1)and(i1s2=top))and(bb) then begin s1:=sum[i2s1]+(cross(origin,convex[i2s1],origin,ip2)+cross(origin,ip2,origin,ip1)+cross(origin,ip1,origin,convex[1])); bb:=false; end;
if ((i2s1=1)and(i2s2=top))and(bb) then begin s1:=sum[i1s1]+(cross(origin,convex[i1s1],origin,ip1)+cross(origin,ip1,origin,ip2)+cross(origin,ip2,origin,convex[1])); bb:=false; end;
if (i1s2<=i2s1)and(bb) then begin s1:=(sum[i2s1]-sum[i1s2])+(cross(origin,convex[i2s1],origin,ip2)+cross(origin,ip2,origin,ip1)+cross(origin,ip1,origin,convex[i1s2])); bb:=false; end;
if (i2s2<=i1s1)and(bb) then begin s1:=(sum[i1s1]-sum[i2s2])+(cross(origin,convex[i1s1],origin,ip1)+cross(origin,ip1,origin,ip2)+cross(origin,ip2,origin,convex[i2s2])); bb:=false; end;
writeln(min(s-s1,s1)/2:0:6);
end;
end;
begin
init;
main;
end.
ewogQXV0aG9yOnd6eDk2MTAwOAogUHJvYmxlbTpzZ3UgMzQ1LVJldm9sdXRpb24KIFZlcmRpY3Q6QWNjZXB0ZWQKIExhbmd1YWdlOlBBU0NBTAogUnVuIFRpbWU6MC43NjVzCiBTdWJtaXNzaW9uIERhdGU6MjYuMDguMTEgMDg6MjUKfQp7JE1PREUgRGVscGhpfQp1c2VzIG1hdGg7CmNvbnN0IGVycm9yPTFlLTg7IG1heG49NTAwMDA7IG9vPTFlMTA7CnR5cGUgcG9pbnQ9cmVjb3JkIHgseTpleHRlbmRlZDsgZW5kOwp2YXIgcHQsY29udmV4OmFycmF5WzEuLm1heG4rMV1vZiBwb2ludDsKICAgIHN1bTphcnJheVsxLi5tYXhuKzFdb2YgZXh0ZW5kZWQ7CiAgICBmczphcnJheVsxLi5tYXhuKjIrMl1vZiBwb2ludDsKICAgIG4sbSx0b3A6bG9uZ2ludDsKICAgIHM6ZXh0ZW5kZWQ7CiAgICBvcmlnaW46cG9pbnQ7CnByb2NlZHVyZSBzd2FwKHZhciBwMSxwMjpwb2ludCk7CnZhciB0OnBvaW50OwpiZWdpbgogdDo9cDE7IHAxOj1wMjsgcDI6PXQ7CmVuZDsKZnVuY3Rpb24gY3Jvc3MocDExLHAxMixwMjEscDIyOnBvaW50KTpleHRlbmRlZDsKdmFyIHgxLHkxLHgyLHkyOmV4dGVuZGVkOwpiZWdpbgogeDE6PXAxMi54LXAxMS54OwogeTE6PXAxMi55LXAxMS55OwogeDI6PXAyMi54LXAyMS54OwogeTI6PXAyMi55LXAyMS55OwogY3Jvc3M6PXgxKnkyLXgyKnkxOwplbmQ7CmZ1bmN0aW9uIGRpc3QocDEscDI6cG9pbnQpOmV4dGVuZGVkOwpiZWdpbgogZGlzdDo9c3FydChzcXIocDEueC1wMi54KStzcXIocDEueS1wMi55KSk7CmVuZDsKcHJvY2VkdXJlIHFzb3J0X3BvbGFyX2FuZ2xlKGwscjpsb25naW50KTsKdmFyIGksajpsb25naW50OwogICAgbTpwb2ludDsKICAgIGNyczEsY3JzMixkc3RtOmV4dGVuZGVkOwpiZWdpbgogaTo9bDsgajo9cjsgbTo9cHRbbCtyYW5kb20oci1sKV07CiByZXBlYXQKICBkc3RtOj1kaXN0KHB0WzFdLG0pOwogIHJlcGVhdAogICBjcnMxOj1jcm9zcyhwdFsxXSxtLHB0WzFdLHB0W2ldKTsKICAgaWYgbm90KChjcnMxPC1lcnJvcilvcigoYWJzKGNyczEpPGVycm9yKWFuZChkc3RtPmRpc3QocHRbMV0scHRbaV0pKSkpIHRoZW4gYnJlYWs7CiAgIGluYyhpKTsKICB1bnRpbCBmYWxzZTsKICByZXBlYXQKICAgY3JzMjo9Y3Jvc3MocHRbMV0scHRbal0scHRbMV0sbSk7CiAgIGlmIG5vdCgoY3JzMjwtZXJyb3Ipb3IoKGFicyhjcnMyKTxlcnJvcilhbmQoZGlzdChwdFsxXSxwdFtqXSk+ZHN0bSkpKSB0aGVuIGJyZWFrOwogICBkZWMoaik7CiAgdW50aWwgZmFsc2U7CiAgaWYgaTw9aiB0aGVuIGJlZ2luCiAgIHN3YXAocHRbaV0scHRbal0pOwogICBpbmMoaSk7IGRlYyhqKTsKICBlbmQ7CiB1bnRpbCBpPmo7CiBpZiBsPGogdGhlbiBxc29ydF9wb2xhcl9hbmdsZShsLGopOwogaWYgaTxyIHRoZW4gcXNvcnRfcG9sYXJfYW5nbGUoaSxyKTsKZW5kOwpwcm9jZWR1cmUgZ2V0X3BvaW50Owp2YXIgaTpsb25naW50OwpiZWdpbgogcmVhZGxuKG4pOwogZm9yIGk6PTEgdG8gbiBkbyBiZWdpbgogIHJlYWRsbihwdFtpXS54LHB0W2ldLnkpOwogIGlmIChwdFtpXS55PHB0WzFdLnkpb3IoKGFicyhwdFtpXS55LXB0WzFdLnkpPGVycm9yKWFuZChwdFtpXS54PHB0WzFdLngpKSB0aGVuIHN3YXAocHRbMV0scHRbaV0pOwogZW5kOwplbmQ7CnByb2NlZHVyZSBnZXRfY29udmV4Owp2YXIgcCxpOmxvbmdpbnQ7CmJlZ2luCiBmb3IgaTo9MSB0byBuIGRvIGJlZ2luCiAgaW5jKHRvcCk7IGNvbnZleFt0b3BdOj1wdFtpXTsKICBpZiB0b3A+MiB0aGVuIGJlZ2luCiAgIHA6PXRvcC0xOwogICB3aGlsZSAocD4xKWFuZChzaWduKGNyb3NzKGNvbnZleFtwLTFdLGNvbnZleFtwXSxjb252ZXhbcF0sY29udmV4W3RvcF0pKTw9MCkgZG8gZGVjKHApOwogICB0b3A6PXArMTsgY29udmV4W3RvcF06PXB0W2ldOwogIGVuZDsKIGVuZDsKZW5kOwpmdW5jdGlvbiBxZChwOnBvaW50KTpsb25naW50OwpiZWdpbgogaWYgKHAueD4wKWFuZChwLnk+PTApIHRoZW4gYmVnaW4gcWQ6PTE7IGV4aXQ7IGVuZDsKIGlmIChwLng8PTApYW5kKHAueT4wKSB0aGVuIGJlZ2luIHFkOj0yOyBleGl0OyBlbmQ7CiBpZiAocC54PDApYW5kKHAueTw9MCkgdGhlbiBiZWdpbiBxZDo9MzsgZXhpdDsgZW5kOwogaWYgKHAueD49MClhbmQocC55PDApIHRoZW4gYmVnaW4gcWQ6PTQ7IGV4aXQ7IGVuZDsKZW5kOwpmdW5jdGlvbiBzbWxlcl9wYShwMTEscDEyLHAyMSxwMjI6cG9pbnQpOmJvb2xlYW47CnZhciB2YzEsdmMyOnBvaW50OwogICAgcWQxLHFkMjpsb25naW50OwpiZWdpbgogdmMxLng6PXAxMi54LXAxMS54OyB2YzEueTo9cDEyLnktcDExLnk7CiB2YzIueDo9cDIyLngtcDIxLng7IHZjMi55Oj1wMjIueS1wMjEueTsKIHFkMTo9cWQodmMxKTsgcWQyOj1xZCh2YzIpOwogaWYgcWQxPD5xZDIgdGhlbiBiZWdpbiBzbWxlcl9wYTo9cWQxPHFkMjsgZXhpdDsgZW5kOwogc21sZXJfcGE6PWNyb3NzKHAxMSxwMTIscDIxLHAyMik+PTA7CmVuZDsKcHJvY2VkdXJlIGluaXQ7CnZhciBpOmxvbmdpbnQ7CmJlZ2luCiBnZXRfcG9pbnQ7CiByYW5kb21pemU7CiBxc29ydF9wb2xhcl9hbmdsZSgyLG4pOwogZ2V0X2NvbnZleDsKIGZvciBpOj0xIHRvIHRvcCBkbyBiZWdpbgogIGZzW2ldOj1jb252ZXhbaV07CiAgZnNbaSt0b3BdOj1jb252ZXhbaV07CiBlbmQ7CiBzdW1bMV06PTA7CiBmb3IgaTo9MiB0byB0b3AgZG8gc3VtW2ldOj1zdW1baS0xXStjcm9zcyhvcmlnaW4sY29udmV4W2ktMV0sb3JpZ2luLGNvbnZleFtpXSk7CiBzOj1zdW1bdG9wXStjcm9zcyhvcmlnaW4sY29udmV4W3RvcF0sb3JpZ2luLGNvbnZleFsxXSk7CmVuZDsKZnVuY3Rpb24gaXRzdChwMSxwMjpwb2ludDsgYSxiLGM6ZXh0ZW5kZWQ7IHZhciBpcDpwb2ludCk6Ym9vbGVhbjsKdmFyIGFhLGJiLGNjLHRtcDpleHRlbmRlZDsKYmVnaW4KIGl0c3Q6PWZhbHNlOwogaWYgc2lnbigoYSpwMS54K2IqcDEueStjKSooYSpwMi54K2IqcDIueStjKSk8PTAgdGhlbiBiZWdpbgogIGl0c3Q6PXRydWU7CiAgYWE6PXAxLnktcDIueTsgYmI6PXAyLngtcDEueDsgY2M6PXAxLngqcDIueS1wMi54KnAxLnk7CiAgdG1wOj1iYiphLWIqYWE7IGlmIHNpZ24odG1wKT0wIHRoZW4gYmVnaW4gaXRzdDo9ZmFsc2U7IGV4aXQ7IGVuZDsKICBpcC54Oj0oYipjYy1jKmJiKS90bXA7CiAgaXAueTo9KGMqYWEtYSpjYykvdG1wOwogZW5kOwplbmQ7CnByb2NlZHVyZSBtYWluOwp2YXIgaSxmcDFuLGZwMm4sY3AxbixjcDJuLGkxczEsaTFzMixpMnMxLGkyczIsdG1wOmxvbmdpbnQ7CiAgICBwMSxwMixpcCxpcDEsaXAyOnBvaW50OwogICAgYSxiLGMsczE6ZXh0ZW5kZWQ7CiAgICBiMSxiMixiYjpib29sZWFuOwpmdW5jdGlvbiBuZXh0KHg6bG9uZ2ludCk6bG9uZ2ludDsKYmVnaW4KIGlmIHg9dG9wIHRoZW4gbmV4dDo9MSBlbHNlIG5leHQ6PXgrMTsKZW5kOwpmdW5jdGlvbiBsYXN0KHg6bG9uZ2ludCk6bG9uZ2ludDsKYmVnaW4KIGlmIHg9MSB0aGVuIGxhc3Q6PXRvcCBlbHNlIGxhc3Q6PXgtMTsKZW5kOwpmdW5jdGlvbiBjaGVjayhwMSxwMjpwb2ludCk6Ym9vbGVhbjsKYmVnaW4KIGNoZWNrOj0oYWJzKHAxLngtcDIueCk8ZXJyb3IpYW5kKGFicyhwMS55LXAyLnkpPGVycm9yKTsKZW5kOwpmdW5jdGlvbiBiaW5hcnlfc2VhcmNoKHAxLHAyOnBvaW50KTpsb25naW50Owp2YXIgbCxyLG06bG9uZ2ludDsKICAgIGIxLGIyOmJvb2xlYW47CiAgICB2ZWM6cG9pbnQ7CmJlZ2luCiB2ZWMueDo9cDIueC1wMS54OyB2ZWMueTo9cDIueS1wMS55OwogaWYgKGNyb3NzKG9yaWdpbix2ZWMsY29udmV4W3RvcF0sY29udmV4WzFdKTw9MClhbmQoY3Jvc3Mob3JpZ2luLHZlYyxjb252ZXhbMV0sY29udmV4WzJdKT49MCkgdGhlbiBiZWdpbiBiaW5hcnlfc2VhcmNoOj0xOyBleGl0OyBlbmQ7CiBpZiAoY3Jvc3Mob3JpZ2luLHZlYyxjb252ZXhbdG9wLTFdLGNvbnZleFt0b3BdKTw9MClhbmQoY3Jvc3Mob3JpZ2luLHZlYyxjb252ZXhbdG9wXSxjb252ZXhbMV0pPj0wKSB0aGVuIGJlZ2luIGJpbmFyeV9zZWFyY2g6PXRvcDsgZXhpdDsgZW5kOwogbDo9MTsgcjo9dG9wOwogd2hpbGUgdHJ1ZSBkbyBiZWdpbgogIG06PShsK3IpIHNociAxOwogIGIxOj1zbWxlcl9wYShjb252ZXhbbS0xXSxjb252ZXhbbV0sb3JpZ2luLHZlYyk7CiAgYjI6PXNtbGVyX3BhKG9yaWdpbix2ZWMsY29udmV4W21dLGNvbnZleFttKzFdKTsKICBpZiAoYjEpYW5kKGIyKSB0aGVuIGJlZ2luIGJpbmFyeV9zZWFyY2g6PW07IGV4aXQ7IGVuZDsKICBpZiAoYjEpYW5kKG5vdChiMikpIHRoZW4gbDo9bTsKICBpZiAobm90KGIxKSlhbmQoYjIpIHRoZW4gcjo9bTsKIGVuZDsKZW5kOwpmdW5jdGlvbiB0cmluYXJ5X3NlYXJjaChsLHI6bG9uZ2ludCk6bG9uZ2ludDsKdmFyIGxsLHJyLHQxLHQyLHQscmV0OmxvbmdpbnQ7CiAgICBmZDEsZmQyLGZkMyxtaW46ZXh0ZW5kZWQ7CmJlZ2luCiBsbDo9bDsgcnI6PXI7CiBpZiByPGwgdGhlbiBycjo9cnIrdG9wOwogd2hpbGUgdHJ1ZSBkbyBiZWdpbgogIHQ6PShyci1sbCkgZGl2IDM7IHQxOj1sbCt0OyB0Mjo9cnItdDsKICBmZDE6PWFicyhhKmZzW3QxXS54K2IqZnNbdDFdLnkrYyk7CiAgZmQyOj1hYnMoYSpmc1t0Ml0ueCtiKmZzW3QyXS55K2MpOwogIGlmIHJyLWxsPD0yIHRoZW4gYmVnaW4KICAgbWluOj1vbzsKICAgaWYgcnItbGw9MiB0aGVuIGJlZ2luCiAgICBmZDM6PWFicyhhKmZzW2xsKzFdLngrYipmc1tsbCsxXS55K2MpOwogICAgaWYgZmQzPG1pbiB0aGVuIGJlZ2luCiAgICAgbWluOj1mZDM7IHJldDo9bGwrMTsKICAgIGVuZDsKICAgZW5kOwogICBpZiBmZDE8bWluIHRoZW4gYmVnaW4KICAgIG1pbjo9ZmQxOyByZXQ6PWxsOwogICBlbmQ7CiAgIGlmIGZkMjxtaW4gdGhlbiBiZWdpbgogICAgbWluOj1mZDI7IHJldDo9cnI7CiAgIGVuZDsKICAgdHJpbmFyeV9zZWFyY2g6PXJldDsgZXhpdDsKICBlbmQ7CiAgaWYgZmQxPGZkMiB0aGVuIHJyOj10MiBlbHNlIGxsOj10MTsKIGVuZDsKZW5kOwpiZWdpbgogcmVhZGxuKG0pOwogZm9yIGk6PTEgdG8gbSBkbyBiZWdpbgogIHJlYWRsbihwMS54LHAxLnkscDIueCxwMi55KTsKICBhOj1wMS55LXAyLnk7IGI6PXAyLngtcDEueDsgYzo9cDEueCpwMi55LXAyLngqcDEueTsKICBmcDFuOj1iaW5hcnlfc2VhcmNoKHAxLHAyKTsKICBmcDJuOj1iaW5hcnlfc2VhcmNoKHAyLHAxKTsKICBjcDFuOj10cmluYXJ5X3NlYXJjaChmcDFuLGZwMm4pOyBpZiBjcDFuPnRvcCB0aGVuIGNwMW46PWNwMW4tdG9wOwogIGNwMm46PXRyaW5hcnlfc2VhcmNoKGZwMm4sZnAxbik7IGlmIGNwMm4+dG9wIHRoZW4gY3Aybjo9Y3Aybi10b3A7CiAgYjE6PXRydWU7IGIyOj10cnVlOwogIGlmIGl0c3QoY29udmV4W2xhc3QoY3AxbildLGNvbnZleFtjcDFuXSxhLGIsYyxpcCkgdGhlbiBiZWdpbgogICBpcDE6PWlwOyBiMTo9ZmFsc2U7IGkxczE6PWxhc3QoY3Axbik7IGkxczI6PWNwMW47CiAgZW5kOwogIGlmIGl0c3QoY29udmV4W2NwMW5dLGNvbnZleFtuZXh0KGNwMW4pXSxhLGIsYyxpcCkgdGhlbiBiZWdpbgogICBpZiBiMSB0aGVuIGJlZ2luIGlwMTo9aXA7IGIxOj1mYWxzZTsgaTFzMTo9Y3AxbjsgaTFzMjo9bmV4dChjcDFuKTsgZW5kOwogICBpZiBub3QoY2hlY2soaXAxLGlwKSlhbmQobm90KGIxKSkgdGhlbiBiZWdpbgogICAgaXAyOj1pcDsgYjI6PWZhbHNlOyBpMnMxOj1jcDFuOyBpMnMyOj1uZXh0KGNwMW4pOwogICBlbmQ7CiAgZW5kOwogIGlmIGl0c3QoY29udmV4W2xhc3QoY3AybildLGNvbnZleFtjcDJuXSxhLGIsYyxpcCkgdGhlbiBiZWdpbgogICBpZiBiMSB0aGVuIGJlZ2luIGlwMTo9aXA7IGIxOj1mYWxzZTsgaTFzMTo9bGFzdChjcDJuKTsgaTFzMjo9Y3AybjsgZW5kOwogICBpZiBub3QoY2hlY2soaXAxLGlwKSlhbmQobm90KGIxKSkgdGhlbiBiZWdpbgogICAgaXAyOj1pcDsgYjI6PWZhbHNlOyBpMnMxOj1sYXN0KGNwMm4pOyBpMnMyOj1jcDJuOwogICBlbmQ7CiAgZW5kOwogIGlmIGl0c3QoY29udmV4W2NwMm5dLGNvbnZleFtuZXh0KGNwMm4pXSxhLGIsYyxpcCkgdGhlbiBiZWdpbgogICBpZiBiMSB0aGVuIGJlZ2luIGlwMTo9aXA7IGIxOj1mYWxzZTsgaTFzMTo9Y3AybjsgaTFzMjo9bmV4dChjcDJuKTsgZW5kOwogICBpZiBub3QoY2hlY2soaXAxLGlwKSlhbmQobm90KGIxKSkgdGhlbiBiZWdpbgogICAgaXAyOj1pcDsgYjI6PWZhbHNlOyBpMnMxOj1jcDJuOyBpMnMyOj1uZXh0KGNwMm4pOwogICBlbmQ7CiAgZW5kOwogIGlmIChiMSlvcihiMikgdGhlbiBiZWdpbiB3cml0ZWxuKCcwLjAwMDAwMCcpOyBjb250aW51ZTsgZW5kOwogIGlmIGkxczE+aTFzMiB0aGVuIGJlZ2luIHRtcDo9aTFzMTsgaTFzMTo9aTFzMjsgaTFzMjo9dG1wOyBlbmQ7CiAgaWYgaTJzMT5pMnMyIHRoZW4gYmVnaW4gdG1wOj1pMnMxOyBpMnMxOj1pMnMyOyBpMnMyOj10bXA7IGVuZDsKICBiYjo9dHJ1ZTsKICBpZiAoKGkxczE9MSlhbmQoaTFzMj10b3ApKWFuZChiYikgdGhlbiBiZWdpbiBzMTo9c3VtW2kyczFdKyhjcm9zcyhvcmlnaW4sY29udmV4W2kyczFdLG9yaWdpbixpcDIpK2Nyb3NzKG9yaWdpbixpcDIsb3JpZ2luLGlwMSkrY3Jvc3Mob3JpZ2luLGlwMSxvcmlnaW4sY29udmV4WzFdKSk7IGJiOj1mYWxzZTsgZW5kOwogIGlmICgoaTJzMT0xKWFuZChpMnMyPXRvcCkpYW5kKGJiKSB0aGVuIGJlZ2luIHMxOj1zdW1baTFzMV0rKGNyb3NzKG9yaWdpbixjb252ZXhbaTFzMV0sb3JpZ2luLGlwMSkrY3Jvc3Mob3JpZ2luLGlwMSxvcmlnaW4saXAyKStjcm9zcyhvcmlnaW4saXAyLG9yaWdpbixjb252ZXhbMV0pKTsgYmI6PWZhbHNlOyBlbmQ7CiAgaWYgKGkxczI8PWkyczEpYW5kKGJiKSB0aGVuIGJlZ2luIHMxOj0oc3VtW2kyczFdLXN1bVtpMXMyXSkrKGNyb3NzKG9yaWdpbixjb252ZXhbaTJzMV0sb3JpZ2luLGlwMikrY3Jvc3Mob3JpZ2luLGlwMixvcmlnaW4saXAxKStjcm9zcyhvcmlnaW4saXAxLG9yaWdpbixjb252ZXhbaTFzMl0pKTsgYmI6PWZhbHNlOyBlbmQ7CiAgaWYgKGkyczI8PWkxczEpYW5kKGJiKSB0aGVuIGJlZ2luIHMxOj0oc3VtW2kxczFdLXN1bVtpMnMyXSkrKGNyb3NzKG9yaWdpbixjb252ZXhbaTFzMV0sb3JpZ2luLGlwMSkrY3Jvc3Mob3JpZ2luLGlwMSxvcmlnaW4saXAyKStjcm9zcyhvcmlnaW4saXAyLG9yaWdpbixjb252ZXhbaTJzMl0pKTsgYmI6PWZhbHNlOyBlbmQ7CiAgd3JpdGVsbihtaW4ocy1zMSxzMSkvMjowOjYpOwogZW5kOwplbmQ7CmJlZ2luCiBpbml0OwogbWFpbjsKZW5kLg==