Artifact Content
Not logged in

Artifact c4b7e5143c129deabe19f6e39b74a9c52bb4f1f8


#include <iostream>
#include <sstream>
#include <iomanip>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <algorithm>
#include <numeric>
#include <iterator>
#include <functional>
#include <complex>
#include <queue>
#include <stack>
#include <cmath>
#include <cassert>
#include <tuple>
using namespace std;
typedef long long LL;
typedef complex<double> CMP;

double outer_prod(const CMP& a, const CMP& b) { return imag(conj(a)*b); }
double inner_prod(const CMP& a, const CMP& b) { return real(conj(a)*b); }

int ccw(const CMP& a, CMP b, CMP c) {
	b -= a; c -= a;
	if( outer_prod(b,c) > 0 ) return +1; // counter clockwise
	if( outer_prod(b,c) < 0 ) return -1; // clockwise
	if( inner_prod(b,c) < 0 ) return +2; // c--a--b on line
	if( norm(b) < norm(c) )   return -2; // a--b--c on line
	return 0;
}

bool byX( const CMP& a, const CMP& b ) {
	if( a.real() != b.real() )
		return a.real() < b.real();
	return a.imag() < b.imag();
}

vector<CMP> convex_hull( vector<CMP> p )
{
	#define IS_RIGHT <0   // skip on-line verts
	//#define IS_RIGHT ==-1 // take all

	sort(p.begin(), p.end(), &byX);

	vector<CMP> ans;
	for(int i=0; i<p.size(); ans.push_back(p[i++])) // left-to-right
		while( ans.size()>=2 && ccw(ans[ans.size()-2], ans[ans.size()-1], p[i]) IS_RIGHT )
			ans.pop_back();
	if( ans.size() == p.size() )
		return ans;
	for(int i=p.size()-2; i>=0; ans.push_back(p[i--])) // right-to-left
		while( ans.size()>=2 && ccw(ans[ans.size()-2], ans[ans.size()-1], p[i]) IS_RIGHT )
			ans.pop_back();
	ans.pop_back();
	return ans;
}

bool point_in_polygon( vector<CMP>& ps, CMP p )
{
	bool in = false;
	for(int i=0; i<ps.size(); ++i) {
		CMP a = ps[i] - p;
		CMP b = ps[(i+1)%ps.size()] - p;
		if(a.imag() > b.imag()) swap(a,b);
		if(a.imag()<=0 && 0<b.imag()) {
			if( outer_prod(a,b) < 0 )
				in = !in;
		}
		//if( outer_prod(a,b)==0 && inner_prod(a,b)<=0 ) return ON;
	}
	return in;
}

class BichromeSky { public:
	double totallyCovered(vector <int> redX, vector <int> redY, vector <int> prob, vector <int> blueX, vector <int> blueY)
	{
		vector<CMP> blue;
		for(int i=0; i<blueX.size(); ++i)
			blue.emplace_back(CMP(blueX[i], blueY[i]));
		blue = convex_hull(blue);

		vector<CMP> red;
		vector<double> p_red;
		for(int i=0; i<redX.size(); ++i) {
			CMP p = CMP(redX[i], redY[i]);
			if(!point_in_polygon(blue, p)) {
				red.emplace_back(p);
				p_red.emplace_back(prob[i] / 1000.0);
			}
		}

		// trivial
		if(red.size() <= 2)
			return 0.0;

		// trivial
		vector<CMP> red_hull = convex_hull(red);
		for(auto p: blue)
			if(!point_in_polygon(red_hull, p))
				return 0.0;

		vector<pair<CMP,double>> rp;
		for(int i=0; i<red.size(); ++i)
			rp.emplace_back(red[i], p_red[i]);
		const int N = rp.size();

		CMP base = *min_element(red.begin(), red.end(), [](const CMP& lhs, const CMP& rhs){
			if(lhs.imag() != rhs.imag()) return lhs.imag() < rhs.imag();
			return lhs.real() < rhs.real();
		});

		sort(rp.begin(), rp.end(), [&](const pair<CMP,double>& lhs, const pair<CMP,double>& rhs) {
			if(lhs == rhs) return false;
			if(lhs.first == base) return true;
			if(rhs.first == base) return false;
			return arg(lhs.first - base) < arg(rhs.first - base);
		});

		function<bool(int,int)> is_right_of_blue = [&](int ai, int bi) {
			CMP a = rp[ai%N].first;
			CMP b = rp[bi%N].first;
			for(CMP p: blue)
				if(ccw(a, b, p) != +1)
					return false;
			return true; // TODO
		};

		function<double(int,int)> rec;
		map<pair<int,int>, double> memo;
		rec = [&](int done_from, int done_to) {
			if(done_from == done_to)
				return 1.0;

			pair<int,int> key(done_from, done_to);
			if(memo.count(key))
				return memo[key];

			double total = 0.0;
			double pp = 1.0;
			for(int next=done_to+1; next<=done_from; ++next) {
				if(is_right_of_blue(done_to, next)) {
					total += pp * (next==done_from ? 1.0 : rp[next].second) * rec(next, done_from);
				}
				pp *= 1.0 - rp[next].second;
			}
			return memo[key] = total;
		};

		double ans = 0.0;
		for(int from=N; from>=2; --from)
		for(int to=1; to<from; ++to) {
			if(is_right_of_blue(from, to)) {
				double pp = 1.0;
				for(int k=(from+1)%N; k!=to; k=(k+1)%N)
					pp *= 1.0 - rp[k].second;
				ans += rp[from%N].second * rp[to].second * pp * rec(from, to);
			}
		}

		return ans;
	}
};

// BEGIN CUT HERE
#include <ctime>
double start_time; string timer()
 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
 { os << "{ ";
   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
void verify_case(const double& Expected, const double& Received) {
 bool ok = (abs(Expected - Received) < 1e-9);
 if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
#define END	 verify_case(_, BichromeSky().totallyCovered(redX, redY, prob, blueX, blueY));}
int main(){

CASE(0)
	int redX_[] = {3,-3,0};
	  vector <int> redX(redX_, redX_+sizeof(redX_)/sizeof(*redX_)); 
	int redY_[] = {-1,-1,2};
	  vector <int> redY(redY_, redY_+sizeof(redY_)/sizeof(*redY_)); 
	int prob_[] = {400,500,600};
	  vector <int> prob(prob_, prob_+sizeof(prob_)/sizeof(*prob_)); 
	int blueX_[] = {1,0,-1};
	  vector <int> blueX(blueX_, blueX_+sizeof(blueX_)/sizeof(*blueX_)); 
	int blueY_[] = {0,1,0};
	  vector <int> blueY(blueY_, blueY_+sizeof(blueY_)/sizeof(*blueY_)); 
	double _ = 0.12; 
END
CASE(1)
	int redX_[] = {3,-3,3,-3};
	  vector <int> redX(redX_, redX_+sizeof(redX_)/sizeof(*redX_)); 
	int redY_[] = {3,3,-3,-3};
	  vector <int> redY(redY_, redY_+sizeof(redY_)/sizeof(*redY_)); 
	int prob_[] = {200,300,400,500};
	  vector <int> prob(prob_, prob_+sizeof(prob_)/sizeof(*prob_)); 
	int blueX_[] = {0,1,-1};
	  vector <int> blueX(blueX_, blueX_+sizeof(blueX_)/sizeof(*blueX_)); 
	int blueY_[] = {-1,-2,-2};
	  vector <int> blueY(blueY_, blueY_+sizeof(blueY_)/sizeof(*blueY_)); 
	double _ = 0.088; 
END
CASE(2)
	int redX_[] = {3,-3,0};
	  vector <int> redX(redX_, redX_+sizeof(redX_)/sizeof(*redX_)); 
	int redY_[] = {-1,-1,2};
	  vector <int> redY(redY_, redY_+sizeof(redY_)/sizeof(*redY_)); 
	int prob_[] = {400,500,600};
	  vector <int> prob(prob_, prob_+sizeof(prob_)/sizeof(*prob_)); 
	int blueX_[] = {1,0,-1,123456};
	  vector <int> blueX(blueX_, blueX_+sizeof(blueX_)/sizeof(*blueX_)); 
	int blueY_[] = {0,1,0,-654321};
	  vector <int> blueY(blueY_, blueY_+sizeof(blueY_)/sizeof(*blueY_)); 
	double _ = 0.0; 
END
CASE(3)
	int redX_[] = {0,-2,-3,-4,-3,-2,0,2,3,4,3,2};
	  vector <int> redX(redX_, redX_+sizeof(redX_)/sizeof(*redX_)); 
	int redY_[] = {4,3,2,0,-2,-3,-4,-3,-2,0,2,3};
	  vector <int> redY(redY_, redY_+sizeof(redY_)/sizeof(*redY_)); 
	int prob_[] = {501,502,503,504,505,506,507,508,509,510,511,512};
	  vector <int> prob(prob_, prob_+sizeof(prob_)/sizeof(*prob_)); 
	int blueX_[] = {1,-1,-1,1};
	  vector <int> blueX(blueX_, blueX_+sizeof(blueX_)/sizeof(*blueX_)); 
	int blueY_[] = {1,1,-1,-1};
	  vector <int> blueY(blueY_, blueY_+sizeof(blueY_)/sizeof(*blueY_)); 
	double _ = 0.6555037822772468; 
END
CASE(4)
	int redX_[] = {0,1,-3,3};
	  vector <int> redX(redX_, redX_+sizeof(redX_)/sizeof(*redX_)); 
	int redY_[] = {0,4,-2,-2};
	  vector <int> redY(redY_, redY_+sizeof(redY_)/sizeof(*redY_)); 
	int prob_[] = {200,300,400,500};
	  vector <int> prob(prob_, prob_+sizeof(prob_)/sizeof(*prob_)); 
	int blueX_[] = {0,-1,1};
	  vector <int> blueX(blueX_, blueX_+sizeof(blueX_)/sizeof(*blueX_)); 
	int blueY_[] = {1,-1,-1};
	  vector <int> blueY(blueY_, blueY_+sizeof(blueY_)/sizeof(*blueY_)); 
	double _ = 0.06; 
END
CASE(5)
	int redX_[] = {10,-17,12,-11,-13,-10,-15,14,-4,2};
	  vector <int> redX(redX_, redX_+sizeof(redX_)/sizeof(*redX_)); 
	int redY_[] = {8,17,-13,-19,-14,11,17,8,-8,-15};
	  vector <int> redY(redY_, redY_+sizeof(redY_)/sizeof(*redY_)); 
	int prob_[] = {412,360,656,876,984,160,368,873,223,128};
	  vector <int> prob(prob_, prob_+sizeof(prob_)/sizeof(*prob_)); 
	int blueX_[] = {-9,-3,6,-9,-5,4,-3,10,-7,2};
	  vector <int> blueX(blueX_, blueX_+sizeof(blueX_)/sizeof(*blueX_)); 
	int blueY_[] = {-6,10,10,-9,-10,-6,2,-10,-9,6};
	  vector <int> blueY(blueY_, blueY_+sizeof(blueY_)/sizeof(*blueY_)); 
	double _ = 0.34037052019900405; 
END
/*
CASE(6)
	int redX_[] = ;
	  vector <int> redX(redX_, redX_+sizeof(redX_)/sizeof(*redX_)); 
	int redY_[] = ;
	  vector <int> redY(redY_, redY_+sizeof(redY_)/sizeof(*redY_)); 
	int prob_[] = ;
	  vector <int> prob(prob_, prob_+sizeof(prob_)/sizeof(*prob_)); 
	int blueX_[] = ;
	  vector <int> blueX(blueX_, blueX_+sizeof(blueX_)/sizeof(*blueX_)); 
	int blueY_[] = ;
	  vector <int> blueY(blueY_, blueY_+sizeof(blueY_)/sizeof(*blueY_)); 
	double _ = ; 
END
CASE(7)
	int redX_[] = ;
	  vector <int> redX(redX_, redX_+sizeof(redX_)/sizeof(*redX_)); 
	int redY_[] = ;
	  vector <int> redY(redY_, redY_+sizeof(redY_)/sizeof(*redY_)); 
	int prob_[] = ;
	  vector <int> prob(prob_, prob_+sizeof(prob_)/sizeof(*prob_)); 
	int blueX_[] = ;
	  vector <int> blueX(blueX_, blueX_+sizeof(blueX_)/sizeof(*blueX_)); 
	int blueY_[] = ;
	  vector <int> blueY(blueY_, blueY_+sizeof(blueY_)/sizeof(*blueY_)); 
	double _ = ; 
END
*/
}
// END CUT HERE