,h,e,n,i);let p=t.prevZ,m=t.nextZ;for(;p&&p.z>=u&&m&&m.z<=d;){if(p!==t.prev&&p!==t.next&&to(r.x,r.y,s.x,s.y,a.x,a.y,p.x,p.y)&&no(p.prev,p,p.next)>=0)return!1;if(p=p.prevZ,m!==t.prev&&m!==t.next&&to(r.x,r.y,s.x,s.y,a.x,a.y,m.x,m.y)&&no(m.prev,m,m.next)>=0)return!1;m=m.nextZ}for(;p&&p.z>=u;){if(p!==t.prev&&p!==t.next&&to(r.x,r.y,s.x,s.y,a.x,a.y,p.x,p.y)&&no(p.prev,p,p.next)>=0)return!1;p=p.prevZ}for(;m&&m.z<=d;){if(m!==t.prev&&m!==t.next&&to(r.x,r.y,s.x,s.y,a.x,a.y,m.x,m.y)&&no(m.prev,m,m.next)>=0)return!1;m=m.nextZ}return!0}function Xa(t,e,n){let i=t;do{const r=i.prev,s=i.next.next;!io(r,s)&&ro(r,i,i.next,s)&&oo(r,s)&&oo(s,r)&&(e.push(r.i/n),e.push(i.i/n),e.push(s.i/n),ho(i),ho(i.next),i=t=s),i=i.next}while(i!==t);return Va(i)}function Ya(t,e,n,i,r,s){let a=t;do{let t=a.next.next;for(;t!==a.prev;){if(a.i!==t.i&&eo(a,t)){let o=lo(a,t);return a=Va(a,a.next),o=Va(o,o.next),Wa(a,e,n,i,r,s),void Wa(o,e,n,i,r,s)}t=t.next}a=a.next}while(a!==t)}function Za(t,e){return t.x-e.x}function Ja(t,e){if(e=function(t,e){let n=e;const i=t.x,r=t.y;let s,a=-1/0;do{if(r<=n.y&&r>=n.next.y&&n.next.y!==n.y){const t=n.x+(r-n.y)*(n.next.x-n.x)/(n.next.y-n.y);if(t<=i&&t>a){if(a=t,t===i){if(r===n.y)return n;if(r===n.next.y)return n.next}s=n.x=n.x&&n.x>=l&&i!==n.x&&to(rs.x||n.x===s.x&&Qa(s,n)))&&(s=n,u=h)),n=n.next}while(n!==o);return s}(t,e)){const n=lo(e,t);Va(e,e.next),Va(n,n.next)}}function Qa(t,e){return no(t.prev,t,e.prev)<0&&no(e.next,t,t.next)<0}function Ka(t,e,n,i,r){return(t=1431655765&((t=858993459&((t=252645135&((t=16711935&((t=32767*(t-n)*r)|t<<8))|t<<4))|t<<2))|t<<1))|(e=1431655765&((e=858993459&((e=252645135&((e=16711935&((e=32767*(e-i)*r)|e<<8))|e<<4))|e<<2))|e<<1))<<1}function $a(t){let e=t,n=t;do{(e.x=0&&(t-a)*(i-o)-(n-a)*(e-o)>=0&&(n-a)*(s-o)-(r-a)*(i-o)>=0}function eo(t,e){return t.next.i!==e.i&&t.prev.i!==e.i&&!function(t,e){let n=t;do{if(n.i!==t.i&&n.next.i!==t.i&&n.i!==e.i&&n.next.i!==e.i&&ro(n,n.next,t,e))return!0;n=n.next}while(n!==t);return!1}(t,e)&&(oo(t,e)&&oo(e,t)&&function(t,e){let n=t,i=!1;const r=(t.x+e.x)/2,s=(t.y+e.y)/2;do{n.y>s!=n.next.y>s&&n.next.y!==n.y&&r<(n.next.x-n.x)*(s-n.y)/(n.next.y-n.y)+n.x&&(i=!i),n=n.next}while(n!==t);return i}(t,e)&&(no(t.prev,t,e.prev)||no(t,e.prev,e))||io(t,e)&&no(t.prev,t,t.next)>0&&no(e.prev,e,e.next)>0)}function no(t,e,n){return(e.y-t.y)*(n.x-e.x)-(e.x-t.x)*(n.y-e.y)}function io(t,e){return t.x===e.x&&t.y===e.y}function ro(t,e,n,i){const r=ao(no(t,e,n)),s=ao(no(t,e,i)),a=ao(no(n,i,t)),o=ao(no(n,i,e));return r!==s&&a!==o||(!(0!==r||!so(t,n,e))||(!(0!==s||!so(t,i,e))||(!(0!==a||!so(n,t,i))||!(0!==o||!so(n,e,i)))))}function so(t,e,n){return e.x<=Math.max(t.x,n.x)&&e.x>=Math.min(t.x,n.x)&&e.y<=Math.max(t.y,n.y)&&e.y>=Math.min(t.y,n.y)}function ao(t){return t>0?1:t<0?-1:0}function oo(t,e){return no(t.prev,t,t.next)<0?no(t,e,t.next)>=0&&no(t,t.prev,e)>=0:no(t,e,t.prev)<0||no(t,t.next,e)<0}function lo(t,e){const n=new uo(t.i,t.x,t.y),i=new uo(e.i,e.x,e.y),r=t.next,s=e.prev;return t.next=e,e.prev=t,n.next=r,r.prev=n,i.next=n,n.prev=i,s.next=i,i.prev=s,i}function co(t,e,n,i){const r=new uo(t,e,n);return i?(r.next=i.next,r.prev=i,i.next.prev=r,i.next=r):(r.prev=r,r.next=r),r}function ho(t){t.next.prev=t.prev,t.prev.next=t.next,t.prevZ&&(t.prevZ.nextZ=t.nextZ),t.nextZ&&(t.nextZ.prevZ=t.prevZ)}function uo(t,e,n){this.i=t,this.x=e,this.y=n,this.prev=null,this.next=null,this.z=null,this.prevZ=null,this.nextZ=null,this.steiner=!1}class po{static area(t){const e=t.length;let n=0;for(let i=e-1,r=0;r2&&t[e-1].equals(t[0])&&t.pop()}function fo(t,e){for(let n=0;n