#include #include #include #include #include #include #include #include #include #include using namespace std; #define EPS 1e-7 class xy{ public: double x; double y; xy() : x(0), y(0) {} xy(double xx, double yy) : x(xx), y(yy) {} xy(const xy& v) : x(v.x), y(v.y){} xy& operator = (const xy& v){ x = v.x; y = v.y; return *this; } xy operator + (const xy& v) const{return xy(this->x+v.x, this->y+v.y);} xy operator - (const xy& v) const{return xy(this->x-v.x, this->y-v.y);} xy operator * (const double& k) const{return xy(this->x * k, this->y * k);} void operator += (const xy& v){x+=v.x; y+=v.y;} void operator -= (const xy& v){x-=v.x; y-=v.y;} void operator *= (const double& k){x*=k; y*=k;} bool operator < (const xy& v) const{ if(x!=v.x) return x < v.x; return y < v.y; } bool operator > (const xy& v) const{ if(x!=v.x) return x > v.x; return y > v.y; } bool operator == (const xy& v) const{ return fabs(x-v.x) + fabs(y-v.y) < EPS; } }; xy operator * (const double& k, const xy& v){return v*k;} //u corss v double cross(const xy& u, const xy& v){ return u.x*v.y - u.y*v.x; } //u dot v double dot(const xy& u, const xy& v){ return u.x*v.x + u.y*v.y; } //distance between two points double dist_p_p(const xy& a, const xy& b){ return sqrt( fabs(dot(a-b, a-b)) ); } //distance between a point and a line segment double dist_p_ls(const xy &p, const xy &s1, const xy &s2){ xy vl = s2 - s1; xy vp = p - s1; return fabs( cross(vl, vp) / sqrt( dot(vl, vl) ) ); } int ccw(xy p1, xy p2, xy p3){ p2 -= p1; p3 -= p1; double c = cross(p2,p3); if( c > EPS /* c > 0 */) return +1; //counter-clockwise if( c < -EPS /* c < 0 */) return -1; //clock-wise if( dot(p2,p3) < -EPS) return +2; //out of segment : p3-p1-p2 if( dot(p3,p3) - dot(p2,p2) > EPS) return -2; //out of segment : p1-p2-p3 return 0; //on the segment : p1-p3-p2 } //are two segment p1-p2 , p3-p4 parallel? bool is_parallel(xy p1, xy p2, xy p3, xy p4){ return abs(ccw(p1,p2, p3))!=1 && abs(ccw(p1,p2, p4))!=1; } //intersect //segment p1-p2, p3-p4 bool inter_ss(xy p1, xy p2, xy p3, xy p4){ int ret1 = ccw(p1,p2, p3) * ccw(p1,p2, p4); int ret2 = ccw(p3,p4, p1) * ccw(p3,p4, p2); return ret1 <= 0 && ret2 <= 0; } bool inter_ss(const pair& l1, const pair& l2){ return inter_ss(l1.first, l1.second, l2.first, l2.second); } //return crossing point l1 and l2 without checking xy inter_point(const pair& l1, const pair& l2){ double a = cross(l2.second - l1.first, l2.second - l2.first); //double b = cross(l1.second - l1.first, l2.second - l1.first); double c = cross(l1.second - l1.first, l2.second - l2.first); double lam = a/c; return l1.first + (l1.second - l1.first)*lam; } //convex_hull //O(n log n) vector convex_hull(vector &v){ if(v.size() == 0){ return {}; } sort( v.begin(), v.end() ); int k = 0; //nums of vertex vector tmp(v.size()*2); //conect i from k for(int i=0; i1 && cross (tmp[k-1] - tmp[k-2], v[i] - tmp[k-1]) <= 0 ) k--; tmp[k] = v[i]; k++; } for(int i=v.size()-2, t=k; i>=0; i--){ while(k>t && cross(tmp[k-1] - tmp[k-2], v[i] - tmp[k-1]) <= 0 ) k--; tmp[k] = v[i]; k++; } tmp.resize(k-1); return tmp; } //O(n) double polygon_area(const vector& poly){ double ret = 0; for(int i=0; i& poly){ bool ret = false; for(int i=0; i=0 && low.y < 0){ if(cross(low,high) > 0) ret = !ret; } if(fabs(cross(low,high)) < EPS && dot(high,low) ostream& operator << (ostream& os, vector vec){ for(int i=0; i istream& operator , (istream& is, T& val){is >> val; return is;} #include int main(){ long long x1,y1,x2,y2, d; cin >> x1,y1,x2,y2,d; assert(d<1000000000); vector rho = {xy(0,d), xy(d,0), xy(0,-d), xy(-d,0)}; vector rec = {xy(x1,y1), xy(x1,y2), xy(x2,y2), xy(x2,y1)}; if(d==0){ cout << (point_inner_polygon(xy(0,0), rec)?1:0) << endl; return 0; } vector p; for(int i=0; i hull = convex_hull(p); double s = polygon_area(hull); long long lattice_b = 0; for(int i=0; i