#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