9298d17feb 2020-08-18        kinaba: #include <iostream>
9298d17feb 2020-08-18        kinaba: #include <sstream>
9298d17feb 2020-08-18        kinaba: #include <iomanip>
9298d17feb 2020-08-18        kinaba: #include <vector>
9298d17feb 2020-08-18        kinaba: #include <string>
9298d17feb 2020-08-18        kinaba: #include <map>
9298d17feb 2020-08-18        kinaba: #include <set>
9298d17feb 2020-08-18        kinaba: #include <algorithm>
9298d17feb 2020-08-18        kinaba: #include <numeric>
9298d17feb 2020-08-18        kinaba: #include <iterator>
9298d17feb 2020-08-18        kinaba: #include <functional>
9298d17feb 2020-08-18        kinaba: #include <complex>
9298d17feb 2020-08-18        kinaba: #include <queue>
9298d17feb 2020-08-18        kinaba: #include <stack>
9298d17feb 2020-08-18        kinaba: #include <cmath>
9298d17feb 2020-08-18        kinaba: #include <cassert>
9298d17feb 2020-08-18        kinaba: #include <tuple>
9298d17feb 2020-08-18        kinaba: using namespace std;
9298d17feb 2020-08-18        kinaba: typedef long long LL;
9298d17feb 2020-08-18        kinaba: typedef complex<double> CMP;
9298d17feb 2020-08-18        kinaba: 
9298d17feb 2020-08-18        kinaba: class RectangularObstacle { public:
9298d17feb 2020-08-18        kinaba: 	long long countReachable(int x1_, int x2_, int y1_, int y2_, int s_)
9298d17feb 2020-08-18        kinaba: 	{
9298d17feb 2020-08-18        kinaba: 		LL x1 = x1_, x2 = x2_, y1 = y1_, y2 = y2_, s=s_;
9298d17feb 2020-08-18        kinaba: 		LL answer = 0;
9298d17feb 2020-08-18        kinaba: 
9298d17feb 2020-08-18        kinaba: 		answer += pyramid(s, s);
9298d17feb 2020-08-18        kinaba: 		answer += 2 * s + 1;
9298d17feb 2020-08-18        kinaba: 		answer += pyramid(s, min(s, y2));
9298d17feb 2020-08-18        kinaba: 
9298d17feb 2020-08-18        kinaba: 		for (LL y=y1; y<=y2 && y<=s; ++y) {
9298d17feb 2020-08-18        kinaba: 		}
9298d17feb 2020-08-18        kinaba: 		// [-s, -1]
9298d17feb 2020-08-18        kinaba: 		//    ==> 1 + 3 + 5 + .. + (2*s-1)
9298d17feb 2020-08-18        kinaba: 		answer += (1LL + 2*s - 1) * s / 2;
9298d17feb 2020-08-18        kinaba: 
9298d17feb 2020-08-18        kinaba: 		// [0, y1-1]
9298d17feb 2020-08-18        kinaba: 		//    ==> (2*s+1) + (2*s-1) + (2*s-3) + ...
9298d17feb 2020-08-18        kinaba: 		LL ymax_case2 = min(y1 - 1, s);
9298d17feb 2020-08-18        kinaba: 		answer += (2 * s + 1 + 2 * (s - ymax_case2) + 1) * (ymax_case2 + 1) / 2;
9298d17feb 2020-08-18        kinaba: 		cerr << answer << endl;
9298d17feb 2020-08-18        kinaba: 		if (s < y1)
9298d17feb 2020-08-18        kinaba: 			return answer;
9298d17feb 2020-08-18        kinaba: 
9298d17feb 2020-08-18        kinaba: 		// [y1, y2]
9298d17feb 2020-08-18        kinaba: 		//    ==> normal, but [x1,x2] subtracted
9298d17feb 2020-08-18        kinaba: 		answer += case3(s - y1, x2, y2 - y1 + 1);
9298d17feb 2020-08-18        kinaba: 		answer += case3(s - y1, -x1, y2 - y1 + 1);
9298d17feb 2020-08-18        kinaba: 		cerr << answer << endl;
9298d17feb 2020-08-18        kinaba: 		if (s <= y2)
9298d17feb 2020-08-18        kinaba: 			return answer;
9298d17feb 2020-08-18        kinaba: 
9298d17feb 2020-08-18        kinaba: 		// [y2+1, +s] : min
9298d17feb 2020-08-18        kinaba: 		//    ==> (0,0) -> (0, y1-1) -> (x2+1, y1-1) -> (x2+1, y) -> (x,y)
9298d17feb 2020-08-18        kinaba: 		//    ==> (0,0) -> (0, y1-1) -> (x1-1, y1-1) -> (x2+1, y) -> (x,y)
9298d17feb 2020-08-18        kinaba: 		LL ls = -x1 + 1 + y2 + 1;  // (x1-1, y2+1)
9298d17feb 2020-08-18        kinaba: 		LL rs = x2 + 1 + y2 + 1;   // (x2+1, y2+1)
9298d17feb 2020-08-18        kinaba: 		answer += case4(x1 - 1, s - ls, x2 + 1, s - rs);
9298d17feb 2020-08-18        kinaba: 		return answer;
9298d17feb 2020-08-18        kinaba: 	}
9298d17feb 2020-08-18        kinaba: 
9298d17feb 2020-08-18        kinaba: 	static LL pyramid(LL s, LL h) {
9298d17feb 2020-08-18        kinaba: 		return (2 * s - 1 + 2 * s - 1 - 2 * h) * h / 2;
9298d17feb 2020-08-18        kinaba: 	}
9298d17feb 2020-08-18        kinaba: 
9298d17feb 2020-08-18        kinaba: 	static LL case3(LL len, LL obs, LL cnt) {
9298d17feb 2020-08-18        kinaba: 		cerr << len << " " << obs << " " << cnt << endl;
9298d17feb 2020-08-18        kinaba: 		cnt = max(0LL, min(cnt, len - obs));
9298d17feb 2020-08-18        kinaba: 		cerr << (len-obs + len-obs - (cnt - 1)) * cnt / 2 << endl;
9298d17feb 2020-08-18        kinaba: 		return (len + len - (cnt - 1)) * cnt / 2;
9298d17feb 2020-08-18        kinaba: 	}
9298d17feb 2020-08-18        kinaba: 
9298d17feb 2020-08-18        kinaba: 	static LL case4(LL x1, LL s1, LL x2, LL s2) {
9298d17feb 2020-08-18        kinaba: 		cerr << x1 << " " << s1 << " " << x2 << " " << s2 << endl;
9298d17feb 2020-08-18        kinaba: 		LL answer = 0;
9298d17feb 2020-08-18        kinaba: 		if (s1 >= 0) answer += simp(s1);
9298d17feb 2020-08-18        kinaba: 		if (s2 >= 0) answer += simp(s2);
9298d17feb 2020-08-18        kinaba: 		if (s1 >= 0 && s2 >= 0) {
9298d17feb 2020-08-18        kinaba: 			LL xl = x2 - s2;
9298d17feb 2020-08-18        kinaba: 			LL xr = x1 + s1;
9298d17feb 2020-08-18        kinaba: 			if (xl <= xr) {
9298d17feb 2020-08-18        kinaba: 				LL w = xr - xl + 1;
9298d17feb 2020-08-18        kinaba: 				answer -= (w + w%2) * (w/2+1) / 2;
9298d17feb 2020-08-18        kinaba: 			}
9298d17feb 2020-08-18        kinaba: 		}
9298d17feb 2020-08-18        kinaba: 		return answer;
9298d17feb 2020-08-18        kinaba: 	}
9298d17feb 2020-08-18        kinaba: 
9298d17feb 2020-08-18        kinaba: 	static LL simp(LL s) {
9298d17feb 2020-08-18        kinaba: 		return (1 + 2 * s + 1) * (s + 1) / 2;
9298d17feb 2020-08-18        kinaba: 	}
9298d17feb 2020-08-18        kinaba: };
9298d17feb 2020-08-18        kinaba: 
9298d17feb 2020-08-18        kinaba: // BEGIN CUT HERE
9298d17feb 2020-08-18        kinaba: #include <ctime>
9298d17feb 2020-08-18        kinaba: double start_time; string timer()
9298d17feb 2020-08-18        kinaba:  { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
9298d17feb 2020-08-18        kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
9298d17feb 2020-08-18        kinaba:  { os << "{ ";
9298d17feb 2020-08-18        kinaba:    for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
9298d17feb 2020-08-18        kinaba:    os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
9298d17feb 2020-08-18        kinaba: void verify_case(const long long& Expected, const long long& Received) {
9298d17feb 2020-08-18        kinaba:  bool ok = (Expected == Received);
9298d17feb 2020-08-18        kinaba:  if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
9298d17feb 2020-08-18        kinaba:  cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
9298d17feb 2020-08-18        kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
9298d17feb 2020-08-18        kinaba: #define END	 verify_case(_, RectangularObstacle().countReachable(x1, x2, y1, y2, s));}
9298d17feb 2020-08-18        kinaba: int main(){
9298d17feb 2020-08-18        kinaba: 
9298d17feb 2020-08-18        kinaba: CASE(0)
9298d17feb 2020-08-18        kinaba: 	int x1 = -5;
9298d17feb 2020-08-18        kinaba: 	int x2 = 5;
9298d17feb 2020-08-18        kinaba: 	int y1 = 3;
9298d17feb 2020-08-18        kinaba: 	int y2 = 3;
9298d17feb 2020-08-18        kinaba: 	int s = 2;
9298d17feb 2020-08-18        kinaba: 	long long _ = 13LL;
9298d17feb 2020-08-18        kinaba: END
9298d17feb 2020-08-18        kinaba: CASE(1)
9298d17feb 2020-08-18        kinaba: 	int x1 = -5;
9298d17feb 2020-08-18        kinaba: 	int x2 = 5;
9298d17feb 2020-08-18        kinaba: 	int y1 = 3;
9298d17feb 2020-08-18        kinaba: 	int y2 = 3;
9298d17feb 2020-08-18        kinaba: 	int s = 3;
9298d17feb 2020-08-18        kinaba: 	long long _ = 24LL;
9298d17feb 2020-08-18        kinaba: END
9298d17feb 2020-08-18        kinaba: CASE(2)
9298d17feb 2020-08-18        kinaba: 	int x1 = -4;
9298d17feb 2020-08-18        kinaba: 	int x2 = 1;
9298d17feb 2020-08-18        kinaba: 	int y1 = 1;
9298d17feb 2020-08-18        kinaba: 	int y2 = 2;
9298d17feb 2020-08-18        kinaba: 	int s = 6;
9298d17feb 2020-08-18        kinaba: 	long long _ = 61LL;
9298d17feb 2020-08-18        kinaba: END
9298d17feb 2020-08-18        kinaba: CASE(3)
9298d17feb 2020-08-18        kinaba: 	int x1 = 0;
9298d17feb 2020-08-18        kinaba: 	int x2 = 0;
9298d17feb 2020-08-18        kinaba: 	int y1 = 1;
9298d17feb 2020-08-18        kinaba: 	int y2 = 1;
9298d17feb 2020-08-18        kinaba: 	int s = 4;
9298d17feb 2020-08-18        kinaba: 	long long _ = 38LL;
9298d17feb 2020-08-18        kinaba: END
9298d17feb 2020-08-18        kinaba: CASE(4)
9298d17feb 2020-08-18        kinaba: 	int x1 = -100;
9298d17feb 2020-08-18        kinaba: 	int x2 = 100;
9298d17feb 2020-08-18        kinaba: 	int y1 = 42;
9298d17feb 2020-08-18        kinaba: 	int y2 = 47;
9298d17feb 2020-08-18        kinaba: 	int s = 0;
9298d17feb 2020-08-18        kinaba: 	long long _ = 1LL;
9298d17feb 2020-08-18        kinaba: END
9298d17feb 2020-08-18        kinaba: CASE(5)
9298d17feb 2020-08-18        kinaba: 	int x1 = -1000000;
9298d17feb 2020-08-18        kinaba: 	int x2 = +1000000;
9298d17feb 2020-08-18        kinaba: 	int y1 = +500000;
9298d17feb 2020-08-18        kinaba: 	int y2 = +1000000;
9298d17feb 2020-08-18        kinaba: 	int s = +1000000000;
9298d17feb 2020-08-18        kinaba: 	long long _ = -1LL;
9298d17feb 2020-08-18        kinaba: END
9298d17feb 2020-08-18        kinaba: CASE(6)
9298d17feb 2020-08-18        kinaba: 	int x1 = -0;
9298d17feb 2020-08-18        kinaba: 	int x2 = +0;
9298d17feb 2020-08-18        kinaba: 	int y1 = 1;
9298d17feb 2020-08-18        kinaba: 	int y2 = 1;
9298d17feb 2020-08-18        kinaba: 	int s = 2;
9298d17feb 2020-08-18        kinaba: 	long long _ = -1LL;
9298d17feb 2020-08-18        kinaba: END
9298d17feb 2020-08-18        kinaba: }
9298d17feb 2020-08-18        kinaba: // END CUT HERE