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