#include #include #include #include #include #include using namespace std; long double const infinity=1e60L, impossible=-infinity; // complexity: O(3^N) struct vec3{ union {struct {int x,y,z;}; int xyz[3];}; vec3(int X=0,int Y=0,int Z=1):x(X),y(Y),z(Z){} int &operator [](int i) {return xyz[i];} int const &operator [](int i) const{return xyz[i];} vec3 operator +(vec3 const &a) const{return {x+a.x,y+a.y,z+a.z};} bool operator <(vec3 const &a) const{return x!=a.x? x 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; // reject parallel lines if (a.x<0) return infinity; // reject negative direction long long yat=ray.y*a.x; // compute y-intercept without the division by ray.x (for integer arithmetic) if (yat verify(vector> walls,vec3 hole,vec3 target){ long double last_distance=0.L; for (int i=0; i<=walls.size(); i++){ pair closest={hypotl(target.x,target.y),-1}; for (int j=i; j dist={intersect(target,walls[j].first,walls[j].second), j}; if (dist.first+1e-8L gen(int x,vector e){ int mask=1; for (int i=e.size(); i--;) mask*=3; set res; while (mask--){ vector a,b; for (int i=0,mosk=mask; i>n; vec3 target; cin>>target.x>>target.y; vector> walls(n); for (auto &i: walls) cin>>i.first.x>>i.first.y>>i.second.x>>i.second.y; vector ex,ey; for (int i=0; i px=gen(target.x,ex); set py=gen(target.y,ey); int res=-1; for (int x: px) for (int y: py){ vec3 aim(x,y); pair result=verify(walls,target,aim); if (result.first!=impossible) res=max(res,result.second); } if (res!=-1){ cout.precision(14); cout<