#include using namespace std; struct vec2{ long double x,y; vec2 operator +(vec2 const &a) const{ return {x+a.x,y+a.y}; } vec2 operator -(vec2 const &a) const{ return {x-a.x,y-a.y}; } vec2 operator *(long double const a) const{ return {x*a,y*a}; } bool operator ==(vec2 const &a) const{ return x==a.x and y==a.y; } long double length() const{ return hypotl(x,y); } void normalize(){ long double l=length(); x/=l; y/=l; } }; long double cross(vec2 const &a,vec2 const &b){ return a.y*b.x-a.x*b.y; } long double dot(vec2 const &a,vec2 const &b){ return a.x*b.x+a.y*b.y; } bool between(pair const &a,pair const &b){ long double c1=cross(a.second-a.first,b.first-a.first); long double c2=cross(a.second-a.first,b.second-a.first); return (c1<=0 and c2>=0) or (c2<=0 and c1>=0); } bool intersects(pair const &a,pair const &b){ return between(a,b) and between(b,a); } vec2 intersection(pair const &a,pair const &b){ if (a.first==b.first or a.first==b.second) return a.first; if (a.second==b.first or a.second==b.second) return a.second; vec2 ad=(a.second-a.first); vec2 bd=(b.second-b.first); vec2 d=b.first-a.first; long double det=cross(ad,bd); if (det){ long double u=cross(d,bd)/det; long double v=cross(d,ad)/det; return a.first+(ad)*u; } else assert(false); } vec2 reflect(vec2 p,pair const &l){ vec2 n=(l.second-l.first); n.normalize(); p=l.first-p; return l.first+p-n*(2*dot(p,n)); } void dump(vector const &v,vector const &dist){ cerr<<"---"<>n; vector v(n*2+4); cin>>v[0].x>>v[0].y; v[1]=v[0]; for (auto it=v.begin()+2; it!=v.begin()+n*2+2; ++it) cin>>it->x>>it->y; cin>>v[n*2+2].x>>v[n*2+2].y; v[n*2+3]=v[n*2+2]; vector dist(n*2+4,1e80L); vector w=v; dist[1]=0; for (int i=2; i=dist[i]){ continue; } bool ok=true; for (int k=(j&~0x1)+2; k/2