#include #include #include #include #include #include using namespace std; typedef __int128 lll; lll const infinity=((lll) 1)<<((lll) 110); static lll gcd(lll a,lll b){return b?gcd(b,a%b):a;} struct fraction{ lll n,d; fraction(lll N,lll D){if (D<0) N=-N, D=-D; lll G=gcd(N,D); n=N/G, d=D/G;} fraction operator+(fraction const a)const{return fraction(n*a.d+a.n*d,d*a.d);} bool operator<(fraction const &a)const{return n/d!=a.n/a.d? n/d b is vertical if (ray.x<0) return intersect({-ray.x,ray.y},{-a.x,a.y},{-b.x,b.y}); // fix case so ray goes to +x if (ray.x==0) return {infinity,1}; // reject parallel lines if (a.x<0) return {infinity,1}; // reject negative direction long long yat=ray.y*a.x; // compute y-intercept without the division by ray.x (for integer arithmetic) if (yat> walls,vec3 hole,vec3 target){ fraction last_distance{0,1}; for (int i=0; i<=walls.size(); i++){ pair closest={fraction(target.x*target.x+target.y*target.y,1),-1}; for (int j=i; j dist={intersect(target,walls[j].first,walls[j].second), j}; if (dist.first>n; vec3 target={}; {int x,y; cin>>x>>y; target.x=x,target.y=y;} vector> walls(n); for (auto &i: walls) {int ax,ay,bx,by; cin>>ax>>ay>>bx>>by; i.first.x=ax,i.first.y=ay,i.second.x=bx,i.second.y=by;} int res=-1; for (int px=-500; px<=500; px++) for (int py=-500; py<=500; py++) if (px!=0 || py!=0) res=max(res,verify(walls,target,vec3{px,py})); res=max(res,verify(walls,target,target)); if (res>=0){ cout<