#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>
using namespace std;
typedef long long LL;
typedef long double LD;
typedef complex<LD> CMP;
struct Ship {
CMP s, e;
LD speed;
LD r;
LD energy;
};
template<typename T>
class IdGen
{
map<T, int> v2id_;
vector<T> id2v_;
public:
int v2id(const T& v) {
if( !v2id_.count(v) ) { v2id_[v] = size(); id2v_.push_back(v); }
return v2id_[v];
}
const T& id2v(int i) const { return id2v_[i]; }
int size() const { return id2v_.size(); }
};
template<typename Vert, typename Flow, int NV=512>
class MaxFlow
{
IdGen<Vert> idgen;
vector<int> G[NV];
Flow F[NV][NV];
public:
void addEdge( Vert s_, Vert t_, Flow f )
{
const int s = idgen.v2id(s_), t = idgen.v2id(t_);
G[s].push_back(t);
G[t].push_back(s);
F[s][t] = f;
F[t][s] = 0;
}
Flow calc( Vert s_, Vert t_ )
{
const int S = idgen.v2id(s_), D = idgen.v2id(t_);
for( Flow total=0 ;; ) {
// Do BFS and compute the level for each node.
int LV[NV] = {0};
vector<int> Q(1, S);
for(int lv=1; !Q.empty(); ++lv) {
vector<int> Q2;
for(size_t i=0; i!=Q.size(); ++i) {
const vector<int>& ne = G[Q[i]];
for(size_t j=0; j!=ne.size(); ++j)
if( F[Q[i]][ne[j]] && !LV[ne[j]] && ne[j]!=S )
LV[ne[j]]=lv, Q2.push_back(ne[j]);
}
Q.swap(Q2);
}
// Destination is now unreachable. Done.
if( !LV[D] )
return total;
// Iterating DFS.
bool blocked[NV] = {};
total += dinic_dfs( S, D, LV, 0x7fffffff, blocked );
}
}
private:
Flow dinic_dfs( int v, int D, int LV[], Flow flow_in, bool blocked[] )
{
Flow flow_out = 0;
for(size_t i=0; i!=G[v].size(); ++i) {
int u = G[v][i];
if( LV[v]+1==LV[u] && F[v][u] ) {
Flow f = min(flow_in-flow_out, F[v][u]);
if( u==D || !blocked[u] && (f=dinic_dfs(u,D,LV,f,blocked))>0 ) {
F[v][u] -= f;
F[u][v] += f;
flow_out += f;
if( flow_in == flow_out ) return flow_out;
}
}
}
blocked[v] = (flow_out==0);
return flow_out;
}
};
bool line_circle(CMP la, CMP lb, CMP c, LD r, CMP* p1, CMP* p2)
{
CMP v = (lb-la) / abs(lb-la);
CMP o = (c-la) / v;
if( abs(o.imag()) > r )
return false;
LD dx = sqrt(r*r - o.imag()*o.imag());
*p1 = la + (o.real()-dx)*v;
*p2 = la + (o.real()+dx)*v;
return true;
}
class EllysDeathStars { public:
double getMax(vector <string> stars_, vector <string> ships_)
{
vector<CMP> stars;
for(int i=0; i<stars_.size(); ++i)
{
stringstream sin(stars_[i]);
int x, y;
sin >> x >> y;
stars.push_back(CMP(x,y));
}
vector<Ship> ships;
for(int i=0; i<ships_.size(); ++i)
{
stringstream sin(ships_[i]);
int sx, sy, ex, ey, s, r, e;
sin >> sx >> sy >> ex >> ey >> s >> r >> e;
Ship ship;
ship.s = CMP(sx,sy);
ship.e = CMP(ex,ey);
if(ship.s == ship.e)
continue;
ship.speed = s;
ship.r = r;
ship.energy = e;
ships.push_back(ship);
}
return solve(stars, ships);
}
LD solve(const vector<CMP>& stars, const vector<Ship>& ships)
{
typedef pair<int, int> Vert;
MaxFlow<Vert, LD, 2048>* mf = new MaxFlow<Vert, LD, 2048>();
for(int b=0; b<ships.size(); ++b)
mf->addEdge(Vert(0,0), Vert(1,b), ships[b].energy);
int id = 0;
for(int a=0; a<stars.size(); ++a) {
vector<LD> events;
events.push_back(0);
for(int b=0; b<ships.size(); ++b)
events.push_back(abs(ships[b].e-ships[b].s) / ships[b].speed);
LD lasttime = *max_element(events.begin(), events.end());
for(int b=0; b<ships.size(); ++b) {
CMP p = ships[b].s;
CMP q = ships[b].e;
CMP o = stars[a];
LD r = ships[b].r;
LD speed = ships[b].speed;
o = (o - p) / ((q-p) / abs(q-p));
LD y = abs(o.imag());
if( y < r ) {
LD dx = sqrt(r*r - y*y);
LD x1 = o.real() - dx;
LD x2 = o.real() + dx;
if(0<x1/speed && x1/speed<lasttime)
events.push_back( x1 / speed );
if(0<x2/speed && x2/speed<lasttime)
events.push_back( x2 / speed );
}
}
sort(events.begin(), events.end());
for(int i=0; i+1<events.size(); ++i, ++id) {
LD sec = events[i+1] - events[i];
LD mid = (events[i+1] + events[i]) / 2;
for(int b=0; b<ships.size(); ++b) {
LD rng = abs(ships[b].e - ships[b].s) / ships[b].speed;
CMP pos = ships[b].s + (ships[b].e-ships[b].s)/abs(ships[b].e-ships[b].s)*ships[b].speed*mid;
if( 0<mid && mid<rng && abs(pos-stars[a])<ships[b].r)
mf->addEdge(Vert(1,b), Vert(2,id), sec);
}
mf->addEdge(Vert(2,id), Vert(3,0), sec);
}
}
LD flow = mf->calc(Vert(0,0), Vert(3,0));
delete mf;
return flow;
}
};
// BEGIN CUT HERE
#include <ctime>
LD 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 LD& Expected, const LD& 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(_, EllysDeathStars().getMax(stars, ships));}
int main(){
CASE(0)
string stars_[] = {"2 2"};
vector <string> stars(stars_, stars_+sizeof(stars_)/sizeof(*stars_));
string ships_[] = {"1 1 5 3 2 1 2"};
vector <string> ships(ships_, ships_+sizeof(ships_)/sizeof(*ships_));
LD _ = 0.894427190999916;
END
CASE(1)
string stars_[] = {"12 10", "7 5"};
vector <string> stars(stars_, stars_+sizeof(stars_)/sizeof(*stars_));
string ships_[] = {"10 10 12 10 1 1 3", "6 1 8 10 1 2 3", "3 6 8 2 5 3 1", "42 42 42 42 6 6 6"};
vector <string> ships(ships_, ships_+sizeof(ships_)/sizeof(*ships_));
LD _ = 4.983770744659944;
END
CASE(2)
string stars_[] = {"5 77", "60 50", "10 46", "22 97", "87 69"};
vector <string> stars(stars_, stars_+sizeof(stars_)/sizeof(*stars_));
string ships_[] = {"42 17 66 11 5 7 13", "10 10 20 20 3 3 3", "13 15 18 9 4 1 2",
"99 71 63 81 19 4 60", "27 34 56 43 11 3 12"};
vector <string> ships(ships_, ships_+sizeof(ships_)/sizeof(*ships_));
LD _ = 0.0;
END
CASE(3)
string stars_[] = {"141 393", "834 847", "568 43", "18 228", "515 794",
"167 283", "849 333", "719 738", "434 261", "613 800",
"127 340", "466 938", "598 601"};
vector <string> stars(stars_, stars_+sizeof(stars_)/sizeof(*stars_));
string ships_[] = {"410 951 472 100 337 226 210", "713 352 677 908 731 687 300",
"191 41 337 92 446 716 213", "598 889 446 907 148 650 203",
"168 556 470 924 344 369 198", "300 182 350 936 737 533 45",
"410 871 488 703 746 631 80", "270 777 636 539 172 103 56",
"466 906 522 98 693 77 309", "768 698 846 110 14 643 14",
"755 724 664 465 263 759 120"};
vector <string> ships(ships_, ships_+sizeof(ships_)/sizeof(*ships_));
LD _ = 31.965770956316362;
END
CASE(4)
string stars_[] =
{"20 1", "70 1", "120 1", "170 1", "220 1", "270 1", "320 1", "370 1", "420 1", "470 1", "520 1", "570 1", "620 1", "670 1", "720 1", "770 1", "820 1", "870 1", "920 1", "970 1"}
;
vector <string> stars(stars_, stars_+sizeof(stars_)/sizeof(*stars_));
string ships_[] =
{"1 21 1000 21 1 21 257", "1 20 1000 20 1 21 102", "1 19 1000 19 1 21 75", "1 18 1000 18 1 21 61", "1 17 1000 17 1 21 51", "1 16 1000 16 1 21 44", "1 15 1000 15 1 21 39", "1 14 1000 14 1 21 34", "1 13 1000 13 1 21 30", "1 12 1000 12 1 21 27", "1 11 1000 11 1 21 24", "1 10 1000 10 1 21 21", "1 9 1000 9 1 21 18", "1 8 1000 8 1 21 15", "1 7 1000 7 1 21 13", "1 6 1000 6 1 21 11", "1 5 1000 5 1 21 9", "1 4 1000 4 1 21 7", "1 3 1000 3 1 21 5", "1 2 1000 2 1 21 3"}
;
vector <string> ships(ships_, ships_+sizeof(ships_)/sizeof(*ships_));
LD _ = 837.0709015727234;
END
CASE(5)
string stars_[] = {"8 7", "11 9"};
vector <string> stars(stars_, stars_+sizeof(stars_)/sizeof(*stars_));
string ships_[] = {"11 14 8 10 92 3 3", "12 14 12 6 434 4 6"};
vector <string> ships(ships_, ships_+sizeof(ships_)/sizeof(*ships_));
LD _ = 0.01583636715715995;
END
}
// END CUT HERE