d82ca3d4de 2014-05-29        kinaba: #include <iostream>
d82ca3d4de 2014-05-29        kinaba: #include <sstream>
d82ca3d4de 2014-05-29        kinaba: #include <iomanip>
d82ca3d4de 2014-05-29        kinaba: #include <vector>
d82ca3d4de 2014-05-29        kinaba: #include <string>
d82ca3d4de 2014-05-29        kinaba: #include <map>
d82ca3d4de 2014-05-29        kinaba: #include <set>
d82ca3d4de 2014-05-29        kinaba: #include <algorithm>
d82ca3d4de 2014-05-29        kinaba: #include <numeric>
d82ca3d4de 2014-05-29        kinaba: #include <iterator>
d82ca3d4de 2014-05-29        kinaba: #include <functional>
d82ca3d4de 2014-05-29        kinaba: #include <complex>
d82ca3d4de 2014-05-29        kinaba: #include <queue>
d82ca3d4de 2014-05-29        kinaba: #include <stack>
d82ca3d4de 2014-05-29        kinaba: #include <cmath>
d82ca3d4de 2014-05-29        kinaba: #include <cassert>
d82ca3d4de 2014-05-29        kinaba: #include <tuple>
d82ca3d4de 2014-05-29        kinaba: using namespace std;
d82ca3d4de 2014-05-29        kinaba: typedef long long LL;
d82ca3d4de 2014-05-29        kinaba: typedef complex<double> CMP;
d82ca3d4de 2014-05-29        kinaba: 
d82ca3d4de 2014-05-29        kinaba: class RadioRange { public:
d82ca3d4de 2014-05-29        kinaba: 	double RadiusProbability(vector <int> X, vector <int> Y, vector <int> R, int Z)
d82ca3d4de 2014-05-29        kinaba: 	{
d82ca3d4de 2014-05-29        kinaba: 		vector<pair<double, bool>> ev;
d82ca3d4de 2014-05-29        kinaba: 
d82ca3d4de 2014-05-29        kinaba: 		const int N = X.size();
d82ca3d4de 2014-05-29        kinaba: 		for(int i=0; i<N; ++i)
d82ca3d4de 2014-05-29        kinaba: 		{
d82ca3d4de 2014-05-29        kinaba: 			double x = X[i];
d82ca3d4de 2014-05-29        kinaba: 			double y = Y[i];
d82ca3d4de 2014-05-29        kinaba: 			double r = R[i];
d82ca3d4de 2014-05-29        kinaba: 			double d = sqrt(x*x+y*y);
d82ca3d4de 2014-05-29        kinaba: 			// (s,e) is bad
d82ca3d4de 2014-05-29        kinaba: 			double s = max(0.0, d-r);
d82ca3d4de 2014-05-29        kinaba: 			double e = min(double(Z), d+r);
d82ca3d4de 2014-05-29        kinaba: 			ev.emplace_back(s, true);
d82ca3d4de 2014-05-29        kinaba: 			ev.emplace_back(e, false);
d82ca3d4de 2014-05-29        kinaba: 		}
d82ca3d4de 2014-05-29        kinaba: 
d82ca3d4de 2014-05-29        kinaba: 		double total_bad = 0.0;
d82ca3d4de 2014-05-29        kinaba: 
d82ca3d4de 2014-05-29        kinaba: 		sort(ev.begin(), ev.end());
d82ca3d4de 2014-05-29        kinaba: 		int nest = 0;
d82ca3d4de 2014-05-29        kinaba: 		double prev_beg;
d82ca3d4de 2014-05-29        kinaba: 		for(auto ei: ev) {
d82ca3d4de 2014-05-29        kinaba: 			double x = ei.first;
d82ca3d4de 2014-05-29        kinaba: 			bool beg = ei.second;
d82ca3d4de 2014-05-29        kinaba: 			if(beg) {
d82ca3d4de 2014-05-29        kinaba: 				if(++nest == 1)
d82ca3d4de 2014-05-29        kinaba: 					prev_beg = x;
d82ca3d4de 2014-05-29        kinaba: 			}
d82ca3d4de 2014-05-29        kinaba: 			else {
d82ca3d4de 2014-05-29        kinaba: 				if(--nest == 0)
d82ca3d4de 2014-05-29        kinaba: 					total_bad += (x-prev_beg);
d82ca3d4de 2014-05-29        kinaba: 			}
d82ca3d4de 2014-05-29        kinaba: 		}
d82ca3d4de 2014-05-29        kinaba: 
d82ca3d4de 2014-05-29        kinaba: 		return (Z - total_bad) / Z;
d82ca3d4de 2014-05-29        kinaba: 	}
d82ca3d4de 2014-05-29        kinaba: };
d82ca3d4de 2014-05-29        kinaba: 
d82ca3d4de 2014-05-29        kinaba: // BEGIN CUT HERE
d82ca3d4de 2014-05-29        kinaba: #include <ctime>
d82ca3d4de 2014-05-29        kinaba: double start_time; string timer()
d82ca3d4de 2014-05-29        kinaba:  { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
d82ca3d4de 2014-05-29        kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
d82ca3d4de 2014-05-29        kinaba:  { os << "{ ";
d82ca3d4de 2014-05-29        kinaba:    for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
d82ca3d4de 2014-05-29        kinaba:    os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
d82ca3d4de 2014-05-29        kinaba: void verify_case(const double& Expected, const double& Received) {
d82ca3d4de 2014-05-29        kinaba:  bool ok = (abs(Expected - Received) < 1e-9);
d82ca3d4de 2014-05-29        kinaba:  if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
d82ca3d4de 2014-05-29        kinaba:  cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
d82ca3d4de 2014-05-29        kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
d82ca3d4de 2014-05-29        kinaba: #define END	 verify_case(_, RadioRange().RadiusProbability(X, Y, R, Z));}
d82ca3d4de 2014-05-29        kinaba: int main(){
d82ca3d4de 2014-05-29        kinaba: 
d82ca3d4de 2014-05-29        kinaba: CASE(0)
d82ca3d4de 2014-05-29        kinaba: 	int X_[] = {0};
d82ca3d4de 2014-05-29        kinaba: 	  vector <int> X(X_, X_+sizeof(X_)/sizeof(*X_));
d82ca3d4de 2014-05-29        kinaba: 	int Y_[] = {0};
d82ca3d4de 2014-05-29        kinaba: 	  vector <int> Y(Y_, Y_+sizeof(Y_)/sizeof(*Y_));
d82ca3d4de 2014-05-29        kinaba: 	int R_[] = {5};
d82ca3d4de 2014-05-29        kinaba: 	  vector <int> R(R_, R_+sizeof(R_)/sizeof(*R_));
d82ca3d4de 2014-05-29        kinaba: 	int Z = 10;
d82ca3d4de 2014-05-29        kinaba: 	double _ = 0.5;
d82ca3d4de 2014-05-29        kinaba: END
d82ca3d4de 2014-05-29        kinaba: CASE(1)
d82ca3d4de 2014-05-29        kinaba: 	int X_[] = {0};
d82ca3d4de 2014-05-29        kinaba: 	  vector <int> X(X_, X_+sizeof(X_)/sizeof(*X_));
d82ca3d4de 2014-05-29        kinaba: 	int Y_[] = {0};
d82ca3d4de 2014-05-29        kinaba: 	  vector <int> Y(Y_, Y_+sizeof(Y_)/sizeof(*Y_));
d82ca3d4de 2014-05-29        kinaba: 	int R_[] = {10};
d82ca3d4de 2014-05-29        kinaba: 	  vector <int> R(R_, R_+sizeof(R_)/sizeof(*R_));
d82ca3d4de 2014-05-29        kinaba: 	int Z = 10;
d82ca3d4de 2014-05-29        kinaba: 	double _ = 0.0;
d82ca3d4de 2014-05-29        kinaba: END
d82ca3d4de 2014-05-29        kinaba: CASE(2)
d82ca3d4de 2014-05-29        kinaba: 	int X_[] = {10};
d82ca3d4de 2014-05-29        kinaba: 	  vector <int> X(X_, X_+sizeof(X_)/sizeof(*X_));
d82ca3d4de 2014-05-29        kinaba: 	int Y_[] = {10};
d82ca3d4de 2014-05-29        kinaba: 	  vector <int> Y(Y_, Y_+sizeof(Y_)/sizeof(*Y_));
d82ca3d4de 2014-05-29        kinaba: 	int R_[] = {10};
d82ca3d4de 2014-05-29        kinaba: 	  vector <int> R(R_, R_+sizeof(R_)/sizeof(*R_));
d82ca3d4de 2014-05-29        kinaba: 	int Z = 10;
d82ca3d4de 2014-05-29        kinaba: 	double _ = 0.4142135623730951;
d82ca3d4de 2014-05-29        kinaba: END
d82ca3d4de 2014-05-29        kinaba: CASE(3)
d82ca3d4de 2014-05-29        kinaba: 	int X_[] = {11, -11, 0, 0};
d82ca3d4de 2014-05-29        kinaba: 	  vector <int> X(X_, X_+sizeof(X_)/sizeof(*X_));
d82ca3d4de 2014-05-29        kinaba: 	int Y_[] = {0, 0, 11, -11};
d82ca3d4de 2014-05-29        kinaba: 	  vector <int> Y(Y_, Y_+sizeof(Y_)/sizeof(*Y_));
d82ca3d4de 2014-05-29        kinaba: 	int R_[] = {10, 10, 10, 10};
d82ca3d4de 2014-05-29        kinaba: 	  vector <int> R(R_, R_+sizeof(R_)/sizeof(*R_));
d82ca3d4de 2014-05-29        kinaba: 	int Z = 31;
d82ca3d4de 2014-05-29        kinaba: 	double _ = 0.3548387096774194;
d82ca3d4de 2014-05-29        kinaba: END
d82ca3d4de 2014-05-29        kinaba: CASE(4)
d82ca3d4de 2014-05-29        kinaba: 	int X_[] = {100};
d82ca3d4de 2014-05-29        kinaba: 	  vector <int> X(X_, X_+sizeof(X_)/sizeof(*X_));
d82ca3d4de 2014-05-29        kinaba: 	int Y_[] = {100};
d82ca3d4de 2014-05-29        kinaba: 	  vector <int> Y(Y_, Y_+sizeof(Y_)/sizeof(*Y_));
d82ca3d4de 2014-05-29        kinaba: 	int R_[] = {1};
d82ca3d4de 2014-05-29        kinaba: 	  vector <int> R(R_, R_+sizeof(R_)/sizeof(*R_));
d82ca3d4de 2014-05-29        kinaba: 	int Z = 10;
d82ca3d4de 2014-05-29        kinaba: 	double _ = 1.0;
d82ca3d4de 2014-05-29        kinaba: END
d82ca3d4de 2014-05-29        kinaba: CASE(5)
d82ca3d4de 2014-05-29        kinaba: 	int X_[] = {1000000000};
d82ca3d4de 2014-05-29        kinaba: 	  vector <int> X(X_, X_+sizeof(X_)/sizeof(*X_));
d82ca3d4de 2014-05-29        kinaba: 	int Y_[] = {1000000000};
d82ca3d4de 2014-05-29        kinaba: 	  vector <int> Y(Y_, Y_+sizeof(Y_)/sizeof(*Y_));
d82ca3d4de 2014-05-29        kinaba: 	int R_[] = {1000000000};
d82ca3d4de 2014-05-29        kinaba: 	  vector <int> R(R_, R_+sizeof(R_)/sizeof(*R_));
d82ca3d4de 2014-05-29        kinaba: 	int Z = 1000000000;
d82ca3d4de 2014-05-29        kinaba: 	double _ = 0.41421356237309503;
d82ca3d4de 2014-05-29        kinaba: END
d82ca3d4de 2014-05-29        kinaba: CASE(6)
d82ca3d4de 2014-05-29        kinaba: 	int X_[] = {20, -20, 0, 0};
d82ca3d4de 2014-05-29        kinaba: 	  vector <int> X(X_, X_+sizeof(X_)/sizeof(*X_));
d82ca3d4de 2014-05-29        kinaba: 	int Y_[] = {0, 0, 20, -20};
d82ca3d4de 2014-05-29        kinaba: 	  vector <int> Y(Y_, Y_+sizeof(Y_)/sizeof(*Y_));
d82ca3d4de 2014-05-29        kinaba: 	int R_[] = {50, 50, 50, 50};
d82ca3d4de 2014-05-29        kinaba: 	  vector <int> R(R_, R_+sizeof(R_)/sizeof(*R_));
d82ca3d4de 2014-05-29        kinaba: 	int Z = 100;
d82ca3d4de 2014-05-29        kinaba: 	double _ = 0.3;
d82ca3d4de 2014-05-29        kinaba: END
d82ca3d4de 2014-05-29        kinaba: CASE(7)
d82ca3d4de 2014-05-29        kinaba: 	int X_[] = {0, -60, -62, -60, 63, -97};
d82ca3d4de 2014-05-29        kinaba: 	  vector <int> X(X_, X_+sizeof(X_)/sizeof(*X_));
d82ca3d4de 2014-05-29        kinaba: 	int Y_[] = {-72, 67, 61, -8, -32, 89};
d82ca3d4de 2014-05-29        kinaba: 	  vector <int> Y(Y_, Y_+sizeof(Y_)/sizeof(*Y_));
d82ca3d4de 2014-05-29        kinaba: 	int R_[] = {6, 7, 8, 7, 5, 6};
d82ca3d4de 2014-05-29        kinaba: 	  vector <int> R(R_, R_+sizeof(R_)/sizeof(*R_));
d82ca3d4de 2014-05-29        kinaba: 	int Z = 918;
d82ca3d4de 2014-05-29        kinaba: 	double _ = 0.9407071068962471;
d82ca3d4de 2014-05-29        kinaba: END
d82ca3d4de 2014-05-29        kinaba: /*
d82ca3d4de 2014-05-29        kinaba: CASE(8)
d82ca3d4de 2014-05-29        kinaba: 	int X_[] = ;
d82ca3d4de 2014-05-29        kinaba: 	  vector <int> X(X_, X_+sizeof(X_)/sizeof(*X_));
d82ca3d4de 2014-05-29        kinaba: 	int Y_[] = ;
d82ca3d4de 2014-05-29        kinaba: 	  vector <int> Y(Y_, Y_+sizeof(Y_)/sizeof(*Y_));
d82ca3d4de 2014-05-29        kinaba: 	int R_[] = ;
d82ca3d4de 2014-05-29        kinaba: 	  vector <int> R(R_, R_+sizeof(R_)/sizeof(*R_));
d82ca3d4de 2014-05-29        kinaba: 	int Z = ;
d82ca3d4de 2014-05-29        kinaba: 	double _ = ;
d82ca3d4de 2014-05-29        kinaba: END
d82ca3d4de 2014-05-29        kinaba: CASE(9)
d82ca3d4de 2014-05-29        kinaba: 	int X_[] = ;
d82ca3d4de 2014-05-29        kinaba: 	  vector <int> X(X_, X_+sizeof(X_)/sizeof(*X_));
d82ca3d4de 2014-05-29        kinaba: 	int Y_[] = ;
d82ca3d4de 2014-05-29        kinaba: 	  vector <int> Y(Y_, Y_+sizeof(Y_)/sizeof(*Y_));
d82ca3d4de 2014-05-29        kinaba: 	int R_[] = ;
d82ca3d4de 2014-05-29        kinaba: 	  vector <int> R(R_, R_+sizeof(R_)/sizeof(*R_));
d82ca3d4de 2014-05-29        kinaba: 	int Z = ;
d82ca3d4de 2014-05-29        kinaba: 	double _ = ;
d82ca3d4de 2014-05-29        kinaba: END
d82ca3d4de 2014-05-29        kinaba: */
d82ca3d4de 2014-05-29        kinaba: }
d82ca3d4de 2014-05-29        kinaba: // END CUT HERE