#include using namespace std; using Int = long long; template inline void chmin(T1 &a,T2 b){if(a>b) a=b;} template inline void chmax(T1 &a,T2 b){if(a> (istream &is,Point &p){ is>>p.x>>p.y; return is; } ostream &operator << (ostream &os,Point p){ os< Polygon; istream &operator >> (istream &is,Polygon &p){ for(int i=0;i<(int)p.size();i++) is>>p[i]; return is; } struct Segment{ Point p1,p2; Segment(){} Segment(Point p1, Point p2):p1(p1),p2(p2){} }; typedef Segment Line; istream &operator >> (istream &is,Segment &s){ is>>s.p1>>s.p2; return is; } struct Circle{ Point c; double r; Circle(){} Circle(Point c,double r):c(c),r(r){} }; istream &operator >> (istream &is,Circle &c){ is>>c.c>>c.r; return is; } double norm(Vector a){ return a.x*a.x+a.y*a.y; } double abs(Vector a){ return sqrt(norm(a)); } double dot(Vector a,Vector b){ return a.x*b.x+a.y*b.y; } double cross(Vector a,Vector b){ return a.x*b.y-a.y*b.x; } Point orth(Point p){return Point(-p.y,p.x);} bool isOrthogonal(Vector a,Vector b){ return equals(dot(a,b),0.0); } bool isOrthogonal(Point a1,Point a2,Point b1,Point b2){ return isOrthogonal(a1-a2,b1-b2); } bool isOrthogonal(Segment s1,Segment s2){ return equals(dot(s1.p2-s1.p1,s2.p2-s2.p1),0.0); } bool isParallel(Vector a,Vector b){ return equals(cross(a,b),0.0); } bool isParallel(Point a1,Point a2,Point b1,Point b2){ return isParallel(a1-a2,b1-b2); } bool isParallel(Segment s1,Segment s2){ return equals(cross(s1.p2-s1.p1,s2.p2-s2.p1),0.0); } Point project(Segment s,Point p){ Vector base=s.p2-s.p1; double r=dot(p-s.p1,base)/norm(base); return s.p1+base*r; } Point reflect(Segment s,Point p){ return p+(project(s,p)-p)*2.0; } double arg(Vector p){ return atan2(p.y,p.x); } Vector polar(double a,double r){ return Point(cos(r)*a,sin(r)*a); } int ccw(Point p0,Point p1,Point p2); bool intersectSS(Point p1,Point p2,Point p3,Point p4); bool intersectSS(Segment s1,Segment s2); bool intersectPS(Polygon p,Segment l); int intersectCC(Circle c1,Circle c2); bool intersectSC(Segment s,Circle c); double getDistanceLP(Line l,Point p); double getDistanceSP(Segment s,Point p); double getDistanceSS(Segment s1,Segment s2); Point getCrossPointSS(Segment s1,Segment s2); Point getCrossPointLL(Line l1,Line l2); Polygon getCrossPointCL(Circle c,Line l); Polygon getCrossPointCC(Circle c1,Circle c2); int contains(Polygon g,Point p); Polygon andrewScan(Polygon s); Polygon convex_hull(Polygon ps); double diameter(Polygon s); bool isConvex(Polygon p); double area(Polygon s); Polygon convexCut(Polygon p,Line l); Line bisector(Point p1,Point p2); Vector translate(Vector v,double theta); vector corner(Line l1,Line l2); vector > > segmentArrangement(vector &ss, Polygon &ps); int ccw(Point p0,Point p1,Point p2){ Vector a = p1-p0; Vector b = p2-p0; if(cross(a,b) > EPS) return CCW_COUNTER_CLOCKWISE; if(cross(a,b) < -EPS) return CCW_CLOCKWISE; if(dot(a,b) < -EPS) return CCW_ONLINE_BACK; if(a.norm()r) return ICC_SEPARATE; if(equals(d+c2.r,c1.r)) return ICC_INSCRIBE; if(d+c2.rEPS) return 0; double d1=abs(c.c-s.p1),d2=abs(c.c-s.p2); if(d1c.r+EPS)||(d1>c.r+EPS&&d21u){ if(dot(l.p1-res[0],l.p2-res[0])>0) swap(res[0],res[1]); res.pop_back(); } return res; } Polygon getCrossPointCC(Circle c1,Circle c2){ Polygon p(2); double d=abs(c1.c-c2.c); double a=acos((c1.r*c1.r+d*d-c2.r*c2.r)/(2*c1.r*d)); double t=arg(c2.c-c1.c); p[0]=c1.c+polar(c1.r,t+a); p[1]=c1.c+polar(c1.r,t-a); return p; } // IN:2 ON:1 OUT:0 int contains(Polygon g,Point p){ int n=g.size(); bool x=false; for(int i=0;ib.y) swap(a,b); if(a.y < EPS && EPS < b.y && cross(a,b) > EPS ) x = !x; } return (x?2:0); } Polygon andrewScan(Polygon s){ Polygon u,l; if(s.size()<3) return s; sort(s.begin(),s.end()); u.push_back(s[0]); u.push_back(s[1]); l.push_back(s[s.size()-1]); l.push_back(s[s.size()-2]); for(int i=2;i<(int)s.size();i++){ for(int n=u.size();n>=2&&ccw(u[n-2],u[n-1],s[i])!=CCW_CLOCKWISE;n--){ u.pop_back(); } u.push_back(s[i]); } for(int i=s.size()-3;i>=0;i--){ for(int n=l.size();n>=2&&ccw(l[n-2],l[n-1],s[i])!=CCW_CLOCKWISE;n--){ l.pop_back(); } l.push_back(s[i]); } reverse(l.begin(),l.end()); for(int i=u.size()-2;i>=1;i--) l.push_back(u[i]); return l; } Polygon convex_hull(Polygon ps){ int n=ps.size(); sort(ps.begin(),ps.end(),sort_y); int k=0; Polygon qs(n*2); for(int i=0;i1&&cross(qs[k-1]-qs[k-2],ps[i]-qs[k-1])<0) k--; qs[k++]=ps[i]; } for(int i=n-2,t=k;i>=0;i--){ while(k>t&&cross(qs[k-1]-qs[k-2],ps[i]-qs[k-1])<0) k--; qs[k++]=ps[i]; } qs.resize(k-1); return qs; } double diameter(Polygon s){ Polygon p=s; int n=p.size(); if(n==2) return abs(p[0]-p[1]); int i=0,j=0; for(int k=0;k0) swap(p[0],p[1]); return Line(p[0],p[1]); } Vector translate(Vector v,double theta){ Vector res; res.x=cos(theta)*v.x-sin(theta)*v.y; res.y=sin(theta)*v.x+cos(theta)*v.y; return res; } vector corner(Line l1,Line l2){ vector res; if(isParallel(l1,l2)){ double d=getDistanceLP(l1,l2.p1)/2.0; Vector v1=l1.p2-l1.p1; v1=v1/v1.abs()*d; Point p=l2.p1+translate(v1,90.0*(PI/180.0)); double d1=getDistanceLP(l1,p); double d2=getDistanceLP(l2,p); if(abs(d1-d2)>d){ p=l2.p1+translate(v1,-90.0*(PI/180.0)); } res.push_back(Line(p,p+v1)); }else{ Point p=getCrossPointLL(l1,l2); Vector v1=l1.p2-l1.p1,v2=l2.p2-l2.p1; v1=v1/v1.abs(); v2=v2/v2.abs(); res.push_back(Line(p,p+(v1+v2))); res.push_back(Line(p,p+translate(v1+v2,90.0*(PI/180.0)))); } return res; } Polygon tangent(Circle c1,Point p2){ Circle c2=Circle(p2,sqrt(norm(c1.c-p2)-c1.r*c1.r)); Polygon p=getCrossPointCC(c1,c2); sort(p.begin(),p.end()); return p; } vector tangent(Circle c1,Circle c2){ vector ls; if(c1.r=-1;s-=2){ double h=(c1.r+s*c2.r)/sqrt(g); if(equals(1-h*h,0)){ ls.emplace_back(c1.c+u*c1.r,c1.c+(u+v)*c1.r); }else if(1-h*h>0){ Point uu=u*h,vv=v*sqrt(1-h*h); ls.emplace_back(c1.c+(uu+vv)*c1.r,c2.c-(uu+vv)*c2.r*s); ls.emplace_back(c1.c+(uu-vv)*c1.r,c2.c-(uu-vv)*c2.r*s); } } return ls; } double closest_pair(Polygon &a,int l=0,int r=-1){ if(r<0){ r=a.size(); sort(a.begin(),a.end(),sort_x); } if(r-l<=1) return abs(a[0]-a[1]); int m=(l+r)>>1; double x=a[m].x; double d=min(closest_pair(a,l,m),closest_pair(a,m,r)); inplace_merge(a.begin()+l,a.begin()+m,a.begin()+r,sort_y); Polygon b; for(int i=l;i=d) continue; for(int j=0;j<(int)b.size();j++){ double dy=a[i].y-next(b.rbegin(),j)->y; if(dy>=d) break; d=min(d,abs(a[i]-*next(b.rbegin(),j))); } b.emplace_back(a[i]); } return d; } vector > > segmentArrangement(vector &ss, Polygon &ps){ int n=ss.size(); for(int i=0;i > > G(ps.size()); for(int i=0;i > ls; for(int j=0;j<(int)ps.size();j++) if(getDistanceSP(ss[i],ps[j]) ss,const int INF){ const int BTM = 0; const int LFT = 1; const int RGH = 2; const int TOP = 3; int n=ss.size(); vector ep; for(int i=0;iss[i].p2.x) swap(ss[i].p1,ss[i].p2); ep.emplace_back(ss[i].p1,i,LFT); ep.emplace_back(ss[i].p2,i,RGH); }else{ if(ss[i].p1.y>ss[i].p2.y) swap(ss[i].p1,ss[i].p2); ep.emplace_back(ss[i].p1,i,BTM); ep.emplace_back(ss[i].p2,i,TOP); } } sort(ep.begin(),ep.end()); set bt; bt.insert(INF); int cnt=0; for(int i=0;i dfs= [&](Circle c,Point a,Point b){ Vector va=c.c-a,vb=c.c-b; double f=cross(va,vb),res=0; if(equals(f,0.0)) return res; if(max(abs(va),abs(vb))c.r-EPS) return c.r*c.r*atan2(d.y,d.x); auto u=getCrossPointCS(c,Segment(a,b)); if(u.empty()) return res; if(u.size()>1u&&dot(u[1]-u[0],a-u[0])>0) swap(u[0],u[1]); u.emplace(u.begin(),a); u.emplace_back(b); for(int i=1;i<(int)u.size();i++) res+=dfs(c,u[i-1],u[i]); return res; }; double res=0; for(int i=0;i<(int)ps.size();i++) res+=dfs(c,ps[i],ps[(i+1)%ps.size()]); return res/2; } typedef vector arr; typedef vector mat; double det(mat A){ int n=A.size(); double res=1; for(int i=0;iabs(A[pivot][i])) pivot=j; swap(A[pivot],A[i]); res*=A[i][i]*(i!=pivot?-1:1); if(abs(A[i][i])=i;k--) A[j][k]-=A[i][k]*A[j][i]/A[i][i]; } return res; } bool isTriangle(double a1,double a2,double a3){ if(a1+a2<=a3||a2+a3<=a1||a3+a1<=a2) return 0; return 1; } double tetrahedra(double OA,double OB,double OC,double AB,double AC,double BC){ if(!isTriangle(OA,OB,AB)) return 0; if(!isTriangle(OB,OC,BC)) return 0; if(!isTriangle(OC,OA,AC)) return 0; if(!isTriangle(AB,AC,BC)) return 0; mat A(5,arr(5,0)); A[0][0]= 0;A[0][1]=AB*AB;A[0][2]=AC*AC;A[0][3]=OA*OA;A[0][4]=1; A[1][0]=AB*AB;A[1][1]= 0;A[1][2]=BC*BC;A[1][3]=OB*OB;A[1][4]=1; A[2][0]=AC*AC;A[2][1]=BC*BC;A[2][2]= 0;A[2][3]=OC*OC;A[2][4]=1; A[3][0]=OA*OA;A[3][1]=OB*OB;A[3][2]=OC*OC;A[3][3]= 0;A[3][4]=1; A[4][0]= 1;A[4][1]= 1;A[4][2]= 1;A[4][3]= 1;A[4][4]=0; //cout<<"det(A):"< xs(4),ys(4),zs(4); for(int i=0;i<4;i++) cin>>xs[i]>>ys[i]>>zs[i]; auto dist=[](double a,double b,double c){return sqrt(a*a+b*b+c*c);}; Point A(0,0); Point B(dist(xs[0]-xs[1],ys[0]-ys[1],zs[0]-zs[1]),0); double ra=dist(xs[0]-xs[2],ys[0]-ys[2],zs[0]-zs[2]); double rb=dist(xs[1]-xs[2],ys[1]-ys[2],zs[1]-zs[2]); Point C=getCrossPointCC(Circle(A,ra),Circle(B,rb))[0]; if(C.y<0) C.y*=-1; double da=dist(xs[0]-xs[3],ys[0]-ys[3],zs[0]-zs[3]); double db=dist(xs[1]-xs[3],ys[1]-ys[3],zs[1]-zs[3]); double dc=dist(xs[2]-xs[3],ys[2]-ys[3],zs[2]-zs[3]); Polygon ps({A,B,C}); double L=tetrahedra(da,db,dc,abs(B),abs(C),abs(B-C))/area(ps)*3; double ea=sqrt(da*da-L*L); double eb=sqrt(db*db-L*L); double ec=sqrt(dc*dc-L*L); Circle ca(A,ea); Circle cb(B,eb); Circle cc(C,ec); Point D; for(Point q:getCrossPointCC(ca,cb)){ if(abs(q-C)<=ec+EPS){ D=q; } } /* cout<EPS); cout<<(contains(ps,D)?"YES":"NO")<