0000: 23 69 6e 63 6c 75 64 65 20 3c 69 6f 73 74 72 65 #include <iostre
0010: 61 6d 3e 0d 0a 23 69 6e 63 6c 75 64 65 20 3c 73 am>..#include <s
0020: 73 74 72 65 61 6d 3e 0d 0a 23 69 6e 63 6c 75 64 stream>..#includ
0030: 65 20 3c 69 6f 6d 61 6e 69 70 3e 0d 0a 23 69 6e e <iomanip>..#in
0040: 63 6c 75 64 65 20 3c 76 65 63 74 6f 72 3e 0d 0a clude <vector>..
0050: 23 69 6e 63 6c 75 64 65 20 3c 73 74 72 69 6e 67 #include <string
0060: 3e 0d 0a 23 69 6e 63 6c 75 64 65 20 3c 6d 61 70 >..#include <map
0070: 3e 0d 0a 23 69 6e 63 6c 75 64 65 20 3c 73 65 74 >..#include <set
0080: 3e 0d 0a 23 69 6e 63 6c 75 64 65 20 3c 61 6c 67 >..#include <alg
0090: 6f 72 69 74 68 6d 3e 0d 0a 23 69 6e 63 6c 75 64 orithm>..#includ
00a0: 65 20 3c 6e 75 6d 65 72 69 63 3e 0d 0a 23 69 6e e <numeric>..#in
00b0: 63 6c 75 64 65 20 3c 69 74 65 72 61 74 6f 72 3e clude <iterator>
00c0: 0d 0a 23 69 6e 63 6c 75 64 65 20 3c 66 75 6e 63 ..#include <func
00d0: 74 69 6f 6e 61 6c 3e 0d 0a 23 69 6e 63 6c 75 64 tional>..#includ
00e0: 65 20 3c 63 6f 6d 70 6c 65 78 3e 0d 0a 23 69 6e e <complex>..#in
00f0: 63 6c 75 64 65 20 3c 71 75 65 75 65 3e 0d 0a 23 clude <queue>..#
0100: 69 6e 63 6c 75 64 65 20 3c 73 74 61 63 6b 3e 0d include <stack>.
0110: 0a 23 69 6e 63 6c 75 64 65 20 3c 63 6d 61 74 68 .#include <cmath
0120: 3e 0d 0a 23 69 6e 63 6c 75 64 65 20 3c 63 61 73 >..#include <cas
0130: 73 65 72 74 3e 0d 0a 75 73 69 6e 67 20 6e 61 6d sert>..using nam
0140: 65 73 70 61 63 65 20 73 74 64 3b 0d 0a 74 79 70 espace std;..typ
0150: 65 64 65 66 20 6c 6f 6e 67 20 6c 6f 6e 67 20 4c edef long long L
0160: 4c 3b 0d 0a 74 79 70 65 64 65 66 20 6c 6f 6e 67 L;..typedef long
0170: 20 64 6f 75 62 6c 65 20 4c 44 3b 0d 0a 74 79 70 double LD;..typ
0180: 65 64 65 66 20 63 6f 6d 70 6c 65 78 3c 4c 44 3e edef complex<LD>
0190: 20 43 4d 50 3b 0d 0a 0d 0a 73 74 72 75 63 74 20 CMP;....struct
01a0: 53 68 69 70 20 7b 0d 0a 09 43 4d 50 20 73 2c 20 Ship {...CMP s,
01b0: 65 3b 0d 0a 09 4c 44 20 73 70 65 65 64 3b 0d 0a e;...LD speed;..
01c0: 09 4c 44 20 72 3b 0d 0a 09 4c 44 20 65 6e 65 72 .LD r;...LD ener
01d0: 67 79 3b 0d 0a 7d 3b 0d 0a 0d 0a 74 65 6d 70 6c gy;..};....templ
01e0: 61 74 65 3c 74 79 70 65 6e 61 6d 65 20 54 3e 0d ate<typename T>.
01f0: 0a 63 6c 61 73 73 20 49 64 47 65 6e 0d 0a 7b 0d .class IdGen..{.
0200: 0a 09 6d 61 70 3c 54 2c 20 69 6e 74 3e 20 76 32 ..map<T, int> v2
0210: 69 64 5f 3b 0d 0a 09 76 65 63 74 6f 72 3c 54 3e id_;...vector<T>
0220: 20 20 20 69 64 32 76 5f 3b 0d 0a 70 75 62 6c 69 id2v_;..publi
0230: 63 3a 0d 0a 09 69 6e 74 20 76 32 69 64 28 63 6f c:...int v2id(co
0240: 6e 73 74 20 54 26 20 76 29 20 7b 0d 0a 09 09 69 nst T& v) {....i
0250: 66 28 20 21 76 32 69 64 5f 2e 63 6f 75 6e 74 28 f( !v2id_.count(
0260: 76 29 20 29 20 7b 20 76 32 69 64 5f 5b 76 5d 20 v) ) { v2id_[v]
0270: 3d 20 73 69 7a 65 28 29 3b 20 69 64 32 76 5f 2e = size(); id2v_.
0280: 70 75 73 68 5f 62 61 63 6b 28 76 29 3b 20 7d 0d push_back(v); }.
0290: 0a 09 09 72 65 74 75 72 6e 20 76 32 69 64 5f 5b ...return v2id_[
02a0: 76 5d 3b 0d 0a 09 7d 0d 0a 09 63 6f 6e 73 74 20 v];...}...const
02b0: 54 26 20 69 64 32 76 28 69 6e 74 20 69 29 20 63 T& id2v(int i) c
02c0: 6f 6e 73 74 20 7b 20 72 65 74 75 72 6e 20 69 64 onst { return id
02d0: 32 76 5f 5b 69 5d 3b 20 7d 0d 0a 09 69 6e 74 20 2v_[i]; }...int
02e0: 73 69 7a 65 28 29 20 63 6f 6e 73 74 20 7b 20 72 size() const { r
02f0: 65 74 75 72 6e 20 69 64 32 76 5f 2e 73 69 7a 65 eturn id2v_.size
0300: 28 29 3b 20 7d 0d 0a 7d 3b 0d 0a 0d 0a 74 65 6d (); }..};....tem
0310: 70 6c 61 74 65 3c 74 79 70 65 6e 61 6d 65 20 56 plate<typename V
0320: 65 72 74 2c 20 74 79 70 65 6e 61 6d 65 20 46 6c ert, typename Fl
0330: 6f 77 2c 20 69 6e 74 20 4e 56 3d 35 31 32 3e 0d ow, int NV=512>.
0340: 0a 63 6c 61 73 73 20 4d 61 78 46 6c 6f 77 0d 0a .class MaxFlow..
0350: 7b 0d 0a 09 49 64 47 65 6e 3c 56 65 72 74 3e 20 {...IdGen<Vert>
0360: 69 64 67 65 6e 3b 0d 0a 09 76 65 63 74 6f 72 3c idgen;...vector<
0370: 69 6e 74 3e 20 47 5b 4e 56 5d 3b 0d 0a 09 46 6c int> G[NV];...Fl
0380: 6f 77 20 46 5b 4e 56 5d 5b 4e 56 5d 3b 0d 0a 0d ow F[NV][NV];...
0390: 0a 70 75 62 6c 69 63 3a 0d 0a 09 76 6f 69 64 20 .public:...void
03a0: 61 64 64 45 64 67 65 28 20 56 65 72 74 20 73 5f addEdge( Vert s_
03b0: 2c 20 56 65 72 74 20 74 5f 2c 20 46 6c 6f 77 20 , Vert t_, Flow
03c0: 66 20 29 0d 0a 09 7b 0d 0a 09 09 63 6f 6e 73 74 f )...{....const
03d0: 20 69 6e 74 20 73 20 3d 20 69 64 67 65 6e 2e 76 int s = idgen.v
03e0: 32 69 64 28 73 5f 29 2c 20 74 20 3d 20 69 64 67 2id(s_), t = idg
03f0: 65 6e 2e 76 32 69 64 28 74 5f 29 3b 0d 0a 09 09 en.v2id(t_);....
0400: 47 5b 73 5d 2e 70 75 73 68 5f 62 61 63 6b 28 74 G[s].push_back(t
0410: 29 3b 0d 0a 09 09 47 5b 74 5d 2e 70 75 73 68 5f );....G[t].push_
0420: 62 61 63 6b 28 73 29 3b 0d 0a 09 09 46 5b 73 5d back(s);....F[s]
0430: 5b 74 5d 20 3d 20 66 3b 0d 0a 09 09 46 5b 74 5d [t] = f;....F[t]
0440: 5b 73 5d 20 3d 20 30 3b 0d 0a 09 7d 0d 0a 0d 0a [s] = 0;...}....
0450: 09 46 6c 6f 77 20 63 61 6c 63 28 20 56 65 72 74 .Flow calc( Vert
0460: 20 73 5f 2c 20 56 65 72 74 20 74 5f 20 29 0d 0a s_, Vert t_ )..
0470: 09 7b 0d 0a 09 09 63 6f 6e 73 74 20 69 6e 74 20 .{....const int
0480: 53 20 3d 20 69 64 67 65 6e 2e 76 32 69 64 28 73 S = idgen.v2id(s
0490: 5f 29 2c 20 44 20 3d 20 69 64 67 65 6e 2e 76 32 _), D = idgen.v2
04a0: 69 64 28 74 5f 29 3b 0d 0a 09 09 66 6f 72 28 20 id(t_);....for(
04b0: 46 6c 6f 77 20 74 6f 74 61 6c 3d 30 20 3b 3b 20 Flow total=0 ;;
04c0: 29 20 7b 0d 0a 09 09 09 2f 2f 20 44 6f 20 42 46 ) {.....// Do BF
04d0: 53 20 61 6e 64 20 63 6f 6d 70 75 74 65 20 74 68 S and compute th
04e0: 65 20 6c 65 76 65 6c 20 66 6f 72 20 65 61 63 68 e level for each
04f0: 20 6e 6f 64 65 2e 0d 0a 09 09 09 69 6e 74 20 4c node......int L
0500: 56 5b 4e 56 5d 20 3d 20 7b 30 7d 3b 0d 0a 09 09 V[NV] = {0};....
0510: 09 76 65 63 74 6f 72 3c 69 6e 74 3e 20 51 28 31 .vector<int> Q(1
0520: 2c 20 53 29 3b 0d 0a 09 09 09 66 6f 72 28 69 6e , S);.....for(in
0530: 74 20 6c 76 3d 31 3b 20 21 51 2e 65 6d 70 74 79 t lv=1; !Q.empty
0540: 28 29 3b 20 2b 2b 6c 76 29 20 7b 0d 0a 09 09 09 (); ++lv) {.....
0550: 09 76 65 63 74 6f 72 3c 69 6e 74 3e 20 51 32 3b .vector<int> Q2;
0560: 0d 0a 09 09 09 09 66 6f 72 28 73 69 7a 65 5f 74 ......for(size_t
0570: 20 69 3d 30 3b 20 69 21 3d 51 2e 73 69 7a 65 28 i=0; i!=Q.size(
0580: 29 3b 20 2b 2b 69 29 20 7b 0d 0a 09 09 09 09 09 ); ++i) {.......
0590: 63 6f 6e 73 74 20 76 65 63 74 6f 72 3c 69 6e 74 const vector<int
05a0: 3e 26 20 6e 65 20 3d 20 47 5b 51 5b 69 5d 5d 3b >& ne = G[Q[i]];
05b0: 0d 0a 09 09 09 09 09 66 6f 72 28 73 69 7a 65 5f .......for(size_
05c0: 74 20 6a 3d 30 3b 20 6a 21 3d 6e 65 2e 73 69 7a t j=0; j!=ne.siz
05d0: 65 28 29 3b 20 2b 2b 6a 29 0d 0a 09 09 09 09 09 e(); ++j).......
05e0: 09 69 66 28 20 46 5b 51 5b 69 5d 5d 5b 6e 65 5b .if( F[Q[i]][ne[
05f0: 6a 5d 5d 20 26 26 20 21 4c 56 5b 6e 65 5b 6a 5d j]] && !LV[ne[j]
0600: 5d 20 26 26 20 6e 65 5b 6a 5d 21 3d 53 20 29 0d ] && ne[j]!=S ).
0610: 0a 09 09 09 09 09 09 09 4c 56 5b 6e 65 5b 6a 5d ........LV[ne[j]
0620: 5d 3d 6c 76 2c 20 51 32 2e 70 75 73 68 5f 62 61 ]=lv, Q2.push_ba
0630: 63 6b 28 6e 65 5b 6a 5d 29 3b 0d 0a 09 09 09 09 ck(ne[j]);......
0640: 7d 0d 0a 09 09 09 09 51 2e 73 77 61 70 28 51 32 }......Q.swap(Q2
0650: 29 3b 0d 0a 09 09 09 7d 0d 0a 0d 0a 09 09 09 2f );.....}......./
0660: 2f 20 44 65 73 74 69 6e 61 74 69 6f 6e 20 69 73 / Destination is
0670: 20 6e 6f 77 20 75 6e 72 65 61 63 68 61 62 6c 65 now unreachable
0680: 2e 20 44 6f 6e 65 2e 0d 0a 09 09 09 69 66 28 20 . Done......if(
0690: 21 4c 56 5b 44 5d 20 29 0d 0a 09 09 09 09 72 65 !LV[D] )......re
06a0: 74 75 72 6e 20 74 6f 74 61 6c 3b 0d 0a 0d 0a 09 turn total;.....
06b0: 09 09 2f 2f 20 49 74 65 72 61 74 69 6e 67 20 44 ..// Iterating D
06c0: 46 53 2e 0d 0a 09 09 09 62 6f 6f 6c 20 62 6c 6f FS......bool blo
06d0: 63 6b 65 64 5b 4e 56 5d 20 3d 20 7b 7d 3b 0d 0a cked[NV] = {};..
06e0: 09 09 09 74 6f 74 61 6c 20 2b 3d 20 64 69 6e 69 ...total += dini
06f0: 63 5f 64 66 73 28 20 53 2c 20 44 2c 20 4c 56 2c c_dfs( S, D, LV,
0700: 20 30 78 37 66 66 66 66 66 66 66 2c 20 62 6c 6f 0x7fffffff, blo
0710: 63 6b 65 64 20 29 3b 0d 0a 09 09 7d 0d 0a 09 7d cked );....}...}
0720: 0d 0a 0d 0a 70 72 69 76 61 74 65 3a 0d 0a 09 46 ....private:...F
0730: 6c 6f 77 20 64 69 6e 69 63 5f 64 66 73 28 20 69 low dinic_dfs( i
0740: 6e 74 20 76 2c 20 69 6e 74 20 44 2c 20 69 6e 74 nt v, int D, int
0750: 20 4c 56 5b 5d 2c 20 46 6c 6f 77 20 66 6c 6f 77 LV[], Flow flow
0760: 5f 69 6e 2c 20 62 6f 6f 6c 20 62 6c 6f 63 6b 65 _in, bool blocke
0770: 64 5b 5d 20 29 0d 0a 09 7b 0d 0a 09 09 46 6c 6f d[] )...{....Flo
0780: 77 20 66 6c 6f 77 5f 6f 75 74 20 3d 20 30 3b 0d w flow_out = 0;.
0790: 0a 09 09 66 6f 72 28 73 69 7a 65 5f 74 20 69 3d ...for(size_t i=
07a0: 30 3b 20 69 21 3d 47 5b 76 5d 2e 73 69 7a 65 28 0; i!=G[v].size(
07b0: 29 3b 20 2b 2b 69 29 20 7b 0d 0a 09 09 09 69 6e ); ++i) {.....in
07c0: 74 20 75 20 3d 20 47 5b 76 5d 5b 69 5d 3b 0d 0a t u = G[v][i];..
07d0: 09 09 09 69 66 28 20 4c 56 5b 76 5d 2b 31 3d 3d ...if( LV[v]+1==
07e0: 4c 56 5b 75 5d 20 26 26 20 46 5b 76 5d 5b 75 5d LV[u] && F[v][u]
07f0: 20 29 20 7b 0d 0a 09 09 09 09 46 6c 6f 77 20 66 ) {......Flow f
0800: 20 3d 20 6d 69 6e 28 66 6c 6f 77 5f 69 6e 2d 66 = min(flow_in-f
0810: 6c 6f 77 5f 6f 75 74 2c 20 46 5b 76 5d 5b 75 5d low_out, F[v][u]
0820: 29 3b 0d 0a 09 09 09 09 69 66 28 20 75 3d 3d 44 );......if( u==D
0830: 20 7c 7c 20 21 62 6c 6f 63 6b 65 64 5b 75 5d 20 || !blocked[u]
0840: 26 26 20 28 66 3d 64 69 6e 69 63 5f 64 66 73 28 && (f=dinic_dfs(
0850: 75 2c 44 2c 4c 56 2c 66 2c 62 6c 6f 63 6b 65 64 u,D,LV,f,blocked
0860: 29 29 3e 30 20 29 20 7b 0d 0a 09 09 09 09 09 46 ))>0 ) {.......F
0870: 5b 76 5d 5b 75 5d 20 20 2d 3d 20 66 3b 0d 0a 09 [v][u] -= f;...
0880: 09 09 09 09 46 5b 75 5d 5b 76 5d 20 20 2b 3d 20 ....F[u][v] +=
0890: 66 3b 0d 0a 09 09 09 09 09 66 6c 6f 77 5f 6f 75 f;.......flow_ou
08a0: 74 20 2b 3d 20 66 3b 0d 0a 09 09 09 09 09 69 66 t += f;.......if
08b0: 28 20 66 6c 6f 77 5f 69 6e 20 3d 3d 20 66 6c 6f ( flow_in == flo
08c0: 77 5f 6f 75 74 20 29 20 72 65 74 75 72 6e 20 66 w_out ) return f
08d0: 6c 6f 77 5f 6f 75 74 3b 0d 0a 09 09 09 09 7d 0d low_out;......}.
08e0: 0a 09 09 09 7d 0d 0a 09 09 7d 0d 0a 09 09 62 6c ....}....}....bl
08f0: 6f 63 6b 65 64 5b 76 5d 20 3d 20 28 66 6c 6f 77 ocked[v] = (flow
0900: 5f 6f 75 74 3d 3d 30 29 3b 0d 0a 09 09 72 65 74 _out==0);....ret
0910: 75 72 6e 20 66 6c 6f 77 5f 6f 75 74 3b 0d 0a 09 urn flow_out;...
0920: 7d 0d 0a 7d 3b 0d 0a 0d 0a 62 6f 6f 6c 20 6c 69 }..};....bool li
0930: 6e 65 5f 63 69 72 63 6c 65 28 43 4d 50 20 6c 61 ne_circle(CMP la
0940: 2c 20 43 4d 50 20 6c 62 2c 20 43 4d 50 20 63 2c , CMP lb, CMP c,
0950: 20 4c 44 20 72 2c 20 43 4d 50 2a 20 70 31 2c 20 LD r, CMP* p1,
0960: 43 4d 50 2a 20 70 32 29 0d 0a 7b 0d 0a 09 43 4d CMP* p2)..{...CM
0970: 50 20 76 20 3d 20 28 6c 62 2d 6c 61 29 20 2f 20 P v = (lb-la) /
0980: 61 62 73 28 6c 62 2d 6c 61 29 3b 0d 0a 09 43 4d abs(lb-la);...CM
0990: 50 20 6f 20 3d 20 28 63 2d 6c 61 29 20 2f 20 76 P o = (c-la) / v
09a0: 3b 0d 0a 09 69 66 28 20 61 62 73 28 6f 2e 69 6d ;...if( abs(o.im
09b0: 61 67 28 29 29 20 3e 20 72 20 29 0d 0a 09 09 72 ag()) > r )....r
09c0: 65 74 75 72 6e 20 66 61 6c 73 65 3b 0d 0a 09 4c eturn false;...L
09d0: 44 20 64 78 20 3d 20 73 71 72 74 28 72 2a 72 20 D dx = sqrt(r*r
09e0: 2d 20 6f 2e 69 6d 61 67 28 29 2a 6f 2e 69 6d 61 - o.imag()*o.ima
09f0: 67 28 29 29 3b 0d 0a 09 2a 70 31 20 3d 20 6c 61 g());...*p1 = la
0a00: 20 2b 20 28 6f 2e 72 65 61 6c 28 29 2d 64 78 29 + (o.real()-dx)
0a10: 2a 76 3b 0d 0a 09 2a 70 32 20 3d 20 6c 61 20 2b *v;...*p2 = la +
0a20: 20 28 6f 2e 72 65 61 6c 28 29 2b 64 78 29 2a 76 (o.real()+dx)*v
0a30: 3b 0d 0a 09 72 65 74 75 72 6e 20 74 72 75 65 3b ;...return true;
0a40: 0d 0a 7d 0d 0a 0d 0a 63 6c 61 73 73 20 45 6c 6c ..}....class Ell
0a50: 79 73 44 65 61 74 68 53 74 61 72 73 20 7b 20 70 ysDeathStars { p
0a60: 75 62 6c 69 63 3a 0d 0a 09 64 6f 75 62 6c 65 20 ublic:...double
0a70: 67 65 74 4d 61 78 28 76 65 63 74 6f 72 20 3c 73 getMax(vector <s
0a80: 74 72 69 6e 67 3e 20 73 74 61 72 73 5f 2c 20 76 tring> stars_, v
0a90: 65 63 74 6f 72 20 3c 73 74 72 69 6e 67 3e 20 73 ector <string> s
0aa0: 68 69 70 73 5f 29 0d 0a 09 7b 0d 0a 09 09 76 65 hips_)...{....ve
0ab0: 63 74 6f 72 3c 43 4d 50 3e 20 73 74 61 72 73 3b ctor<CMP> stars;
0ac0: 0d 0a 09 09 66 6f 72 28 69 6e 74 20 69 3d 30 3b ....for(int i=0;
0ad0: 20 69 3c 73 74 61 72 73 5f 2e 73 69 7a 65 28 29 i<stars_.size()
0ae0: 3b 20 2b 2b 69 29 0d 0a 09 09 7b 0d 0a 09 09 09 ; ++i)....{.....
0af0: 73 74 72 69 6e 67 73 74 72 65 61 6d 20 73 69 6e stringstream sin
0b00: 28 73 74 61 72 73 5f 5b 69 5d 29 3b 0d 0a 09 09 (stars_[i]);....
0b10: 09 69 6e 74 20 78 2c 20 79 3b 0d 0a 09 09 09 73 .int x, y;.....s
0b20: 69 6e 20 3e 3e 20 78 20 3e 3e 20 79 3b 0d 0a 09 in >> x >> y;...
0b30: 09 09 73 74 61 72 73 2e 70 75 73 68 5f 62 61 63 ..stars.push_bac
0b40: 6b 28 43 4d 50 28 78 2c 79 29 29 3b 0d 0a 09 09 k(CMP(x,y));....
0b50: 7d 0d 0a 09 09 76 65 63 74 6f 72 3c 53 68 69 70 }....vector<Ship
0b60: 3e 20 73 68 69 70 73 3b 0d 0a 09 09 66 6f 72 28 > ships;....for(
0b70: 69 6e 74 20 69 3d 30 3b 20 69 3c 73 68 69 70 73 int i=0; i<ships
0b80: 5f 2e 73 69 7a 65 28 29 3b 20 2b 2b 69 29 0d 0a _.size(); ++i)..
0b90: 09 09 7b 0d 0a 09 09 09 73 74 72 69 6e 67 73 74 ..{.....stringst
0ba0: 72 65 61 6d 20 73 69 6e 28 73 68 69 70 73 5f 5b ream sin(ships_[
0bb0: 69 5d 29 3b 0d 0a 09 09 09 69 6e 74 20 73 78 2c i]);.....int sx,
0bc0: 20 73 79 2c 20 65 78 2c 20 65 79 2c 20 73 2c 20 sy, ex, ey, s,
0bd0: 72 2c 20 65 3b 0d 0a 09 09 09 73 69 6e 20 3e 3e r, e;.....sin >>
0be0: 20 73 78 20 3e 3e 20 73 79 20 3e 3e 20 65 78 20 sx >> sy >> ex
0bf0: 3e 3e 20 65 79 20 3e 3e 20 73 20 3e 3e 20 72 20 >> ey >> s >> r
0c00: 3e 3e 20 65 3b 0d 0a 09 09 09 53 68 69 70 20 73 >> e;.....Ship s
0c10: 68 69 70 3b 0d 0a 09 09 09 73 68 69 70 2e 73 20 hip;.....ship.s
0c20: 3d 20 43 4d 50 28 73 78 2c 73 79 29 3b 0d 0a 09 = CMP(sx,sy);...
0c30: 09 09 73 68 69 70 2e 65 20 3d 20 43 4d 50 28 65 ..ship.e = CMP(e
0c40: 78 2c 65 79 29 3b 0d 0a 09 09 09 69 66 28 73 68 x,ey);.....if(sh
0c50: 69 70 2e 73 20 3d 3d 20 73 68 69 70 2e 65 29 0d ip.s == ship.e).
0c60: 0a 09 09 09 09 63 6f 6e 74 69 6e 75 65 3b 0d 0a .....continue;..
0c70: 09 09 09 73 68 69 70 2e 73 70 65 65 64 20 3d 20 ...ship.speed =
0c80: 73 3b 0d 0a 09 09 09 73 68 69 70 2e 72 20 3d 20 s;.....ship.r =
0c90: 72 3b 0d 0a 09 09 09 73 68 69 70 2e 65 6e 65 72 r;.....ship.ener
0ca0: 67 79 20 3d 20 65 3b 0d 0a 09 09 09 73 68 69 70 gy = e;.....ship
0cb0: 73 2e 70 75 73 68 5f 62 61 63 6b 28 73 68 69 70 s.push_back(ship
0cc0: 29 3b 0d 0a 09 09 7d 0d 0a 09 09 72 65 74 75 72 );....}....retur
0cd0: 6e 20 73 6f 6c 76 65 28 73 74 61 72 73 2c 20 73 n solve(stars, s
0ce0: 68 69 70 73 29 3b 0d 0a 09 7d 0d 0a 0d 0a 09 4c hips);...}.....L
0cf0: 44 20 73 6f 6c 76 65 28 63 6f 6e 73 74 20 76 65 D solve(const ve
0d00: 63 74 6f 72 3c 43 4d 50 3e 26 20 73 74 61 72 73 ctor<CMP>& stars
0d10: 2c 20 63 6f 6e 73 74 20 76 65 63 74 6f 72 3c 53 , const vector<S
0d20: 68 69 70 3e 26 20 73 68 69 70 73 29 0d 0a 09 7b hip>& ships)...{
0d30: 0d 0a 09 09 74 79 70 65 64 65 66 20 70 61 69 72 ....typedef pair
0d40: 3c 69 6e 74 2c 20 69 6e 74 3e 20 56 65 72 74 3b <int, int> Vert;
0d50: 0d 0a 09 09 4d 61 78 46 6c 6f 77 3c 56 65 72 74 ....MaxFlow<Vert
0d60: 2c 20 4c 44 2c 20 32 30 34 38 3e 2a 20 6d 66 20 , LD, 2048>* mf
0d70: 3d 20 6e 65 77 20 4d 61 78 46 6c 6f 77 3c 56 65 = new MaxFlow<Ve
0d80: 72 74 2c 20 4c 44 2c 20 32 30 34 38 3e 28 29 3b rt, LD, 2048>();
0d90: 0d 0a 09 09 66 6f 72 28 69 6e 74 20 62 3d 30 3b ....for(int b=0;
0da0: 20 62 3c 73 68 69 70 73 2e 73 69 7a 65 28 29 3b b<ships.size();
0db0: 20 2b 2b 62 29 0d 0a 09 09 09 6d 66 2d 3e 61 64 ++b).....mf->ad
0dc0: 64 45 64 67 65 28 56 65 72 74 28 30 2c 30 29 2c dEdge(Vert(0,0),
0dd0: 20 56 65 72 74 28 31 2c 62 29 2c 20 73 68 69 70 Vert(1,b), ship
0de0: 73 5b 62 5d 2e 65 6e 65 72 67 79 29 3b 0d 0a 0d s[b].energy);...
0df0: 0a 09 09 69 6e 74 20 69 64 20 3d 20 30 3b 0d 0a ...int id = 0;..
0e00: 09 09 66 6f 72 28 69 6e 74 20 61 3d 30 3b 20 61 ..for(int a=0; a
0e10: 3c 73 74 61 72 73 2e 73 69 7a 65 28 29 3b 20 2b <stars.size(); +
0e20: 2b 61 29 20 7b 0d 0a 09 09 09 76 65 63 74 6f 72 +a) {.....vector
0e30: 3c 4c 44 3e 20 65 76 65 6e 74 73 3b 0d 0a 09 09 <LD> events;....
0e40: 09 65 76 65 6e 74 73 2e 70 75 73 68 5f 62 61 63 .events.push_bac
0e50: 6b 28 30 29 3b 0d 0a 09 09 09 66 6f 72 28 69 6e k(0);.....for(in
0e60: 74 20 62 3d 30 3b 20 62 3c 73 68 69 70 73 2e 73 t b=0; b<ships.s
0e70: 69 7a 65 28 29 3b 20 2b 2b 62 29 0d 0a 09 09 09 ize(); ++b).....
0e80: 09 65 76 65 6e 74 73 2e 70 75 73 68 5f 62 61 63 .events.push_bac
0e90: 6b 28 61 62 73 28 73 68 69 70 73 5b 62 5d 2e 65 k(abs(ships[b].e
0ea0: 2d 73 68 69 70 73 5b 62 5d 2e 73 29 20 2f 20 73 -ships[b].s) / s
0eb0: 68 69 70 73 5b 62 5d 2e 73 70 65 65 64 29 3b 0d hips[b].speed);.
0ec0: 0a 09 09 09 4c 44 20 6c 61 73 74 74 69 6d 65 20 ....LD lasttime
0ed0: 3d 20 2a 6d 61 78 5f 65 6c 65 6d 65 6e 74 28 65 = *max_element(e
0ee0: 76 65 6e 74 73 2e 62 65 67 69 6e 28 29 2c 20 65 vents.begin(), e
0ef0: 76 65 6e 74 73 2e 65 6e 64 28 29 29 3b 0d 0a 0d vents.end());...
0f00: 0a 09 09 09 66 6f 72 28 69 6e 74 20 62 3d 30 3b ....for(int b=0;
0f10: 20 62 3c 73 68 69 70 73 2e 73 69 7a 65 28 29 3b b<ships.size();
0f20: 20 2b 2b 62 29 20 7b 0d 0a 09 09 09 09 43 4d 50 ++b) {......CMP
0f30: 20 70 20 3d 20 73 68 69 70 73 5b 62 5d 2e 73 3b p = ships[b].s;
0f40: 0d 0a 09 09 09 09 43 4d 50 20 71 20 3d 20 73 68 ......CMP q = sh
0f50: 69 70 73 5b 62 5d 2e 65 3b 0d 0a 09 09 09 09 43 ips[b].e;......C
0f60: 4d 50 20 6f 20 3d 20 73 74 61 72 73 5b 61 5d 3b MP o = stars[a];
0f70: 0d 0a 09 09 09 09 4c 44 20 72 20 3d 20 73 68 69 ......LD r = shi
0f80: 70 73 5b 62 5d 2e 72 3b 0d 0a 09 09 09 09 4c 44 ps[b].r;......LD
0f90: 20 73 70 65 65 64 20 3d 20 73 68 69 70 73 5b 62 speed = ships[b
0fa0: 5d 2e 73 70 65 65 64 3b 0d 0a 0d 0a 09 09 09 09 ].speed;........
0fb0: 6f 20 3d 20 28 6f 20 2d 20 70 29 20 2f 20 28 28 o = (o - p) / ((
0fc0: 71 2d 70 29 20 2f 20 61 62 73 28 71 2d 70 29 29 q-p) / abs(q-p))
0fd0: 3b 0d 0a 09 09 09 09 4c 44 20 79 20 3d 20 61 62 ;......LD y = ab
0fe0: 73 28 6f 2e 69 6d 61 67 28 29 29 3b 0d 0a 09 09 s(o.imag());....
0ff0: 09 09 69 66 28 20 79 20 3c 20 72 20 29 20 7b 0d ..if( y < r ) {.
1000: 0a 09 09 09 09 09 4c 44 20 64 78 20 3d 20 73 71 ......LD dx = sq
1010: 72 74 28 72 2a 72 20 2d 20 79 2a 79 29 3b 0d 0a rt(r*r - y*y);..
1020: 09 09 09 09 09 4c 44 20 78 31 20 3d 20 6f 2e 72 .....LD x1 = o.r
1030: 65 61 6c 28 29 20 2d 20 64 78 3b 0d 0a 09 09 09 eal() - dx;.....
1040: 09 09 4c 44 20 78 32 20 3d 20 6f 2e 72 65 61 6c ..LD x2 = o.real
1050: 28 29 20 2b 20 64 78 3b 0d 0a 09 09 09 09 09 69 () + dx;.......i
1060: 66 28 30 3c 78 31 2f 73 70 65 65 64 20 26 26 20 f(0<x1/speed &&
1070: 78 31 2f 73 70 65 65 64 3c 6c 61 73 74 74 69 6d x1/speed<lasttim
1080: 65 29 0d 0a 09 09 09 09 09 09 65 76 65 6e 74 73 e)........events
1090: 2e 70 75 73 68 5f 62 61 63 6b 28 20 78 31 20 2f .push_back( x1 /
10a0: 20 73 70 65 65 64 20 29 3b 0d 0a 09 09 09 09 09 speed );.......
10b0: 69 66 28 30 3c 78 32 2f 73 70 65 65 64 20 26 26 if(0<x2/speed &&
10c0: 20 78 32 2f 73 70 65 65 64 3c 6c 61 73 74 74 69 x2/speed<lastti
10d0: 6d 65 29 0d 0a 09 09 09 09 09 09 65 76 65 6e 74 me)........event
10e0: 73 2e 70 75 73 68 5f 62 61 63 6b 28 20 78 32 20 s.push_back( x2
10f0: 2f 20 73 70 65 65 64 20 29 3b 0d 0a 09 09 09 09 / speed );......
1100: 7d 0d 0a 09 09 09 7d 0d 0a 09 09 09 73 6f 72 74 }.....}.....sort
1110: 28 65 76 65 6e 74 73 2e 62 65 67 69 6e 28 29 2c (events.begin(),
1120: 20 65 76 65 6e 74 73 2e 65 6e 64 28 29 29 3b 0d events.end());.
1130: 0a 0d 0a 09 09 09 66 6f 72 28 69 6e 74 20 69 3d ......for(int i=
1140: 30 3b 20 69 2b 31 3c 65 76 65 6e 74 73 2e 73 69 0; i+1<events.si
1150: 7a 65 28 29 3b 20 2b 2b 69 2c 20 2b 2b 69 64 29 ze(); ++i, ++id)
1160: 20 7b 0d 0a 09 09 09 09 4c 44 20 73 65 63 20 3d {......LD sec =
1170: 20 65 76 65 6e 74 73 5b 69 2b 31 5d 20 2d 20 65 events[i+1] - e
1180: 76 65 6e 74 73 5b 69 5d 3b 0d 0a 09 09 09 09 4c vents[i];......L
1190: 44 20 6d 69 64 20 3d 20 28 65 76 65 6e 74 73 5b D mid = (events[
11a0: 69 2b 31 5d 20 2b 20 65 76 65 6e 74 73 5b 69 5d i+1] + events[i]
11b0: 29 20 2f 20 32 3b 0d 0a 09 09 09 09 66 6f 72 28 ) / 2;......for(
11c0: 69 6e 74 20 62 3d 30 3b 20 62 3c 73 68 69 70 73 int b=0; b<ships
11d0: 2e 73 69 7a 65 28 29 3b 20 2b 2b 62 29 20 7b 0d .size(); ++b) {.
11e0: 0a 09 09 09 09 09 4c 44 20 72 6e 67 20 3d 20 61 ......LD rng = a
11f0: 62 73 28 73 68 69 70 73 5b 62 5d 2e 65 20 2d 20 bs(ships[b].e -
1200: 73 68 69 70 73 5b 62 5d 2e 73 29 20 2f 20 73 68 ships[b].s) / sh
1210: 69 70 73 5b 62 5d 2e 73 70 65 65 64 3b 0d 0a 09 ips[b].speed;...
1220: 09 09 09 09 43 4d 50 20 70 6f 73 20 3d 20 73 68 ....CMP pos = sh
1230: 69 70 73 5b 62 5d 2e 73 20 2b 20 28 73 68 69 70 ips[b].s + (ship
1240: 73 5b 62 5d 2e 65 2d 73 68 69 70 73 5b 62 5d 2e s[b].e-ships[b].
1250: 73 29 2f 61 62 73 28 73 68 69 70 73 5b 62 5d 2e s)/abs(ships[b].
1260: 65 2d 73 68 69 70 73 5b 62 5d 2e 73 29 2a 73 68 e-ships[b].s)*sh
1270: 69 70 73 5b 62 5d 2e 73 70 65 65 64 2a 6d 69 64 ips[b].speed*mid
1280: 3b 0d 0a 09 09 09 09 09 69 66 28 20 30 3c 6d 69 ;.......if( 0<mi
1290: 64 20 26 26 20 6d 69 64 3c 72 6e 67 20 26 26 20 d && mid<rng &&
12a0: 61 62 73 28 70 6f 73 2d 73 74 61 72 73 5b 61 5d abs(pos-stars[a]
12b0: 29 3c 73 68 69 70 73 5b 62 5d 2e 72 29 0d 0a 09 )<ships[b].r)...
12c0: 09 09 09 09 09 6d 66 2d 3e 61 64 64 45 64 67 65 .....mf->addEdge
12d0: 28 56 65 72 74 28 31 2c 62 29 2c 20 56 65 72 74 (Vert(1,b), Vert
12e0: 28 32 2c 69 64 29 2c 20 73 65 63 29 3b 0d 0a 09 (2,id), sec);...
12f0: 09 09 09 7d 0d 0a 09 09 09 09 6d 66 2d 3e 61 64 ...}......mf->ad
1300: 64 45 64 67 65 28 56 65 72 74 28 32 2c 69 64 29 dEdge(Vert(2,id)
1310: 2c 20 56 65 72 74 28 33 2c 30 29 2c 20 73 65 63 , Vert(3,0), sec
1320: 29 3b 0d 0a 09 09 09 7d 0d 0a 09 09 7d 0d 0a 0d );.....}....}...
1330: 0a 09 09 4c 44 20 66 6c 6f 77 20 3d 20 6d 66 2d ...LD flow = mf-
1340: 3e 63 61 6c 63 28 56 65 72 74 28 30 2c 30 29 2c >calc(Vert(0,0),
1350: 20 56 65 72 74 28 33 2c 30 29 29 3b 0d 0a 09 09 Vert(3,0));....
1360: 64 65 6c 65 74 65 20 6d 66 3b 0d 0a 09 09 72 65 delete mf;....re
1370: 74 75 72 6e 20 66 6c 6f 77 3b 0d 0a 09 7d 0d 0a turn flow;...}..
1380: 7d 3b 0d 0a 0d 0a 2f 2f 20 42 45 47 49 4e 20 43 };....// BEGIN C
1390: 55 54 20 48 45 52 45 0d 0a 23 69 6e 63 6c 75 64 UT HERE..#includ
13a0: 65 20 3c 63 74 69 6d 65 3e 0d 0a 4c 44 20 73 74 e <ctime>..LD st
13b0: 61 72 74 5f 74 69 6d 65 3b 20 73 74 72 69 6e 67 art_time; string
13c0: 20 74 69 6d 65 72 28 29 0d 0a 20 7b 20 6f 73 74 timer().. { ost
13d0: 72 69 6e 67 73 74 72 65 61 6d 20 6f 73 3b 20 6f ringstream os; o
13e0: 73 20 3c 3c 20 22 20 28 22 20 3c 3c 20 69 6e 74 s << " (" << int
13f0: 28 28 63 6c 6f 63 6b 28 29 2d 73 74 61 72 74 5f ((clock()-start_
1400: 74 69 6d 65 29 2f 43 4c 4f 43 4b 53 5f 50 45 52 time)/CLOCKS_PER
1410: 5f 53 45 43 2a 31 30 30 30 29 20 3c 3c 20 22 20 _SEC*1000) << "
1420: 6d 73 65 63 29 22 3b 20 72 65 74 75 72 6e 20 6f msec)"; return o
1430: 73 2e 73 74 72 28 29 3b 20 7d 0d 0a 74 65 6d 70 s.str(); }..temp
1440: 6c 61 74 65 3c 74 79 70 65 6e 61 6d 65 20 54 3e late<typename T>
1450: 20 6f 73 74 72 65 61 6d 26 20 6f 70 65 72 61 74 ostream& operat
1460: 6f 72 3c 3c 28 6f 73 74 72 65 61 6d 26 20 6f 73 or<<(ostream& os
1470: 2c 20 63 6f 6e 73 74 20 76 65 63 74 6f 72 3c 54 , const vector<T
1480: 3e 26 20 76 29 0d 0a 20 7b 20 6f 73 20 3c 3c 20 >& v).. { os <<
1490: 22 7b 20 22 3b 0d 0a 20 20 20 66 6f 72 28 74 79 "{ ";.. for(ty
14a0: 70 65 6e 61 6d 65 20 76 65 63 74 6f 72 3c 54 3e pename vector<T>
14b0: 3a 3a 63 6f 6e 73 74 5f 69 74 65 72 61 74 6f 72 ::const_iterator
14c0: 20 69 74 3d 76 2e 62 65 67 69 6e 28 29 3b 20 69 it=v.begin(); i
14d0: 74 21 3d 76 2e 65 6e 64 28 29 3b 20 2b 2b 69 74 t!=v.end(); ++it
14e0: 29 0d 0a 20 20 20 6f 73 20 3c 3c 20 27 5c 22 27 ).. os << '\"'
14f0: 20 3c 3c 20 2a 69 74 20 3c 3c 20 27 5c 22 27 20 << *it << '\"'
1500: 3c 3c 20 28 69 74 2b 31 3d 3d 76 2e 65 6e 64 28 << (it+1==v.end(
1510: 29 20 3f 20 22 22 20 3a 20 22 2c 20 22 29 3b 20 ) ? "" : ", ");
1520: 6f 73 20 3c 3c 20 22 20 7d 22 3b 20 72 65 74 75 os << " }"; retu
1530: 72 6e 20 6f 73 3b 20 7d 0d 0a 76 6f 69 64 20 76 rn os; }..void v
1540: 65 72 69 66 79 5f 63 61 73 65 28 63 6f 6e 73 74 erify_case(const
1550: 20 4c 44 26 20 45 78 70 65 63 74 65 64 2c 20 63 LD& Expected, c
1560: 6f 6e 73 74 20 4c 44 26 20 52 65 63 65 69 76 65 onst LD& Receive
1570: 64 29 20 7b 0d 0a 20 62 6f 6f 6c 20 6f 6b 20 3d d) {.. bool ok =
1580: 20 28 61 62 73 28 45 78 70 65 63 74 65 64 20 2d (abs(Expected -
1590: 20 52 65 63 65 69 76 65 64 29 20 3c 20 31 65 2d Received) < 1e-
15a0: 39 29 3b 0d 0a 20 69 66 28 6f 6b 29 20 63 65 72 9);.. if(ok) cer
15b0: 72 20 3c 3c 20 22 50 41 53 53 45 44 22 20 3c 3c r << "PASSED" <<
15c0: 20 74 69 6d 65 72 28 29 20 3c 3c 20 65 6e 64 6c timer() << endl
15d0: 3b 20 20 65 6c 73 65 20 7b 20 63 65 72 72 20 3c ; else { cerr <
15e0: 3c 20 22 46 41 49 4c 45 44 22 20 3c 3c 20 74 69 < "FAILED" << ti
15f0: 6d 65 72 28 29 20 3c 3c 20 65 6e 64 6c 3b 0d 0a mer() << endl;..
1600: 20 63 65 72 72 20 3c 3c 20 22 5c 74 6f 3a 20 5c cerr << "\to: \
1610: 22 22 20 3c 3c 20 45 78 70 65 63 74 65 64 20 3c "" << Expected <
1620: 3c 20 27 5c 22 27 20 3c 3c 20 65 6e 64 6c 20 3c < '\"' << endl <
1630: 3c 20 22 5c 74 78 3a 20 5c 22 22 20 3c 3c 20 52 < "\tx: \"" << R
1640: 65 63 65 69 76 65 64 20 3c 3c 20 27 5c 22 27 20 eceived << '\"'
1650: 3c 3c 20 65 6e 64 6c 3b 20 7d 20 7d 0d 0a 23 64 << endl; } }..#d
1660: 65 66 69 6e 65 20 43 41 53 45 28 4e 29 20 7b 63 efine CASE(N) {c
1670: 65 72 72 20 3c 3c 20 22 54 65 73 74 20 43 61 73 err << "Test Cas
1680: 65 20 23 22 20 3c 3c 20 4e 20 3c 3c 20 22 2e 2e e #" << N << "..
1690: 2e 22 20 3c 3c 20 66 6c 75 73 68 3b 20 73 74 61 ." << flush; sta
16a0: 72 74 5f 74 69 6d 65 3d 63 6c 6f 63 6b 28 29 3b rt_time=clock();
16b0: 0d 0a 23 64 65 66 69 6e 65 20 45 4e 44 09 20 76 ..#define END. v
16c0: 65 72 69 66 79 5f 63 61 73 65 28 5f 2c 20 45 6c erify_case(_, El
16d0: 6c 79 73 44 65 61 74 68 53 74 61 72 73 28 29 2e lysDeathStars().
16e0: 67 65 74 4d 61 78 28 73 74 61 72 73 2c 20 73 68 getMax(stars, sh
16f0: 69 70 73 29 29 3b 7d 0d 0a 69 6e 74 20 6d 61 69 ips));}..int mai
1700: 6e 28 29 7b 0d 0a 0d 0a 43 41 53 45 28 30 29 0d n(){....CASE(0).
1710: 0a 09 73 74 72 69 6e 67 20 73 74 61 72 73 5f 5b ..string stars_[
1720: 5d 20 3d 20 7b 22 32 20 32 22 7d 3b 0d 0a 09 20 ] = {"2 2"};...
1730: 20 76 65 63 74 6f 72 20 3c 73 74 72 69 6e 67 3e vector <string>
1740: 20 73 74 61 72 73 28 73 74 61 72 73 5f 2c 20 73 stars(stars_, s
1750: 74 61 72 73 5f 2b 73 69 7a 65 6f 66 28 73 74 61 tars_+sizeof(sta
1760: 72 73 5f 29 2f 73 69 7a 65 6f 66 28 2a 73 74 61 rs_)/sizeof(*sta
1770: 72 73 5f 29 29 3b 20 0d 0a 09 73 74 72 69 6e 67 rs_)); ...string
1780: 20 73 68 69 70 73 5f 5b 5d 20 3d 20 7b 22 31 20 ships_[] = {"1
1790: 31 20 35 20 33 20 32 20 31 20 32 22 7d 3b 0d 0a 1 5 3 2 1 2"};..
17a0: 09 20 20 76 65 63 74 6f 72 20 3c 73 74 72 69 6e . vector <strin
17b0: 67 3e 20 73 68 69 70 73 28 73 68 69 70 73 5f 2c g> ships(ships_,
17c0: 20 73 68 69 70 73 5f 2b 73 69 7a 65 6f 66 28 73 ships_+sizeof(s
17d0: 68 69 70 73 5f 29 2f 73 69 7a 65 6f 66 28 2a 73 hips_)/sizeof(*s
17e0: 68 69 70 73 5f 29 29 3b 20 0d 0a 09 4c 44 20 5f hips_)); ...LD _
17f0: 20 3d 20 30 2e 38 39 34 34 32 37 31 39 30 39 39 = 0.89442719099
1800: 39 39 31 36 3b 20 0d 0a 45 4e 44 0d 0a 43 41 53 9916; ..END..CAS
1810: 45 28 31 29 0d 0a 09 73 74 72 69 6e 67 20 73 74 E(1)...string st
1820: 61 72 73 5f 5b 5d 20 3d 20 7b 22 31 32 20 31 30 ars_[] = {"12 10
1830: 22 2c 20 22 37 20 35 22 7d 3b 0d 0a 09 20 20 76 ", "7 5"};... v
1840: 65 63 74 6f 72 20 3c 73 74 72 69 6e 67 3e 20 73 ector <string> s
1850: 74 61 72 73 28 73 74 61 72 73 5f 2c 20 73 74 61 tars(stars_, sta
1860: 72 73 5f 2b 73 69 7a 65 6f 66 28 73 74 61 72 73 rs_+sizeof(stars
1870: 5f 29 2f 73 69 7a 65 6f 66 28 2a 73 74 61 72 73 _)/sizeof(*stars
1880: 5f 29 29 3b 20 0d 0a 09 73 74 72 69 6e 67 20 73 _)); ...string s
1890: 68 69 70 73 5f 5b 5d 20 3d 20 7b 22 31 30 20 31 hips_[] = {"10 1
18a0: 30 20 31 32 20 31 30 20 31 20 31 20 33 22 2c 20 0 12 10 1 1 3",
18b0: 22 36 20 31 20 38 20 31 30 20 31 20 32 20 33 22 "6 1 8 10 1 2 3"
18c0: 2c 20 22 33 20 36 20 38 20 32 20 35 20 33 20 31 , "3 6 8 2 5 3 1
18d0: 22 2c 20 22 34 32 20 34 32 20 34 32 20 34 32 20 ", "42 42 42 42
18e0: 36 20 36 20 36 22 7d 3b 0d 0a 09 20 20 76 65 63 6 6 6"};... vec
18f0: 74 6f 72 20 3c 73 74 72 69 6e 67 3e 20 73 68 69 tor <string> shi
1900: 70 73 28 73 68 69 70 73 5f 2c 20 73 68 69 70 73 ps(ships_, ships
1910: 5f 2b 73 69 7a 65 6f 66 28 73 68 69 70 73 5f 29 _+sizeof(ships_)
1920: 2f 73 69 7a 65 6f 66 28 2a 73 68 69 70 73 5f 29 /sizeof(*ships_)
1930: 29 3b 20 0d 0a 09 4c 44 20 5f 20 3d 20 34 2e 39 ); ...LD _ = 4.9
1940: 38 33 37 37 30 37 34 34 36 35 39 39 34 34 3b 20 83770744659944;
1950: 0d 0a 45 4e 44 0d 0a 43 41 53 45 28 32 29 0d 0a ..END..CASE(2)..
1960: 09 73 74 72 69 6e 67 20 73 74 61 72 73 5f 5b 5d .string stars_[]
1970: 20 3d 20 7b 22 35 20 37 37 22 2c 20 22 36 30 20 = {"5 77", "60
1980: 35 30 22 2c 20 22 31 30 20 34 36 22 2c 20 22 32 50", "10 46", "2
1990: 32 20 39 37 22 2c 20 22 38 37 20 36 39 22 7d 3b 2 97", "87 69"};
19a0: 0d 0a 09 20 20 76 65 63 74 6f 72 20 3c 73 74 72 ... vector <str
19b0: 69 6e 67 3e 20 73 74 61 72 73 28 73 74 61 72 73 ing> stars(stars
19c0: 5f 2c 20 73 74 61 72 73 5f 2b 73 69 7a 65 6f 66 _, stars_+sizeof
19d0: 28 73 74 61 72 73 5f 29 2f 73 69 7a 65 6f 66 28 (stars_)/sizeof(
19e0: 2a 73 74 61 72 73 5f 29 29 3b 20 0d 0a 09 73 74 *stars_)); ...st
19f0: 72 69 6e 67 20 73 68 69 70 73 5f 5b 5d 20 3d 20 ring ships_[] =
1a00: 7b 22 34 32 20 31 37 20 36 36 20 31 31 20 35 20 {"42 17 66 11 5
1a10: 37 20 31 33 22 2c 20 22 31 30 20 31 30 20 32 30 7 13", "10 10 20
1a20: 20 32 30 20 33 20 33 20 33 22 2c 20 22 31 33 20 20 3 3 3", "13
1a30: 31 35 20 31 38 20 39 20 34 20 31 20 32 22 2c 0d 15 18 9 4 1 2",.
1a40: 0a 20 22 39 39 20 37 31 20 36 33 20 38 31 20 31 . "99 71 63 81 1
1a50: 39 20 34 20 36 30 22 2c 20 22 32 37 20 33 34 20 9 4 60", "27 34
1a60: 35 36 20 34 33 20 31 31 20 33 20 31 32 22 7d 3b 56 43 11 3 12"};
1a70: 0d 0a 09 20 20 76 65 63 74 6f 72 20 3c 73 74 72 ... vector <str
1a80: 69 6e 67 3e 20 73 68 69 70 73 28 73 68 69 70 73 ing> ships(ships
1a90: 5f 2c 20 73 68 69 70 73 5f 2b 73 69 7a 65 6f 66 _, ships_+sizeof
1aa0: 28 73 68 69 70 73 5f 29 2f 73 69 7a 65 6f 66 28 (ships_)/sizeof(
1ab0: 2a 73 68 69 70 73 5f 29 29 3b 20 0d 0a 09 4c 44 *ships_)); ...LD
1ac0: 20 5f 20 3d 20 30 2e 30 3b 20 0d 0a 45 4e 44 0d _ = 0.0; ..END.
1ad0: 0a 43 41 53 45 28 33 29 0d 0a 09 73 74 72 69 6e .CASE(3)...strin
1ae0: 67 20 73 74 61 72 73 5f 5b 5d 20 3d 20 7b 22 31 g stars_[] = {"1
1af0: 34 31 20 33 39 33 22 2c 20 22 38 33 34 20 38 34 41 393", "834 84
1b00: 37 22 2c 20 22 35 36 38 20 34 33 22 2c 20 22 31 7", "568 43", "1
1b10: 38 20 32 32 38 22 2c 20 22 35 31 35 20 37 39 34 8 228", "515 794
1b20: 22 2c 0d 0a 20 22 31 36 37 20 32 38 33 22 2c 20 ",.. "167 283",
1b30: 22 38 34 39 20 33 33 33 22 2c 20 22 37 31 39 20 "849 333", "719
1b40: 37 33 38 22 2c 20 22 34 33 34 20 32 36 31 22 2c 738", "434 261",
1b50: 20 22 36 31 33 20 38 30 30 22 2c 0d 0a 20 22 31 "613 800",.. "1
1b60: 32 37 20 33 34 30 22 2c 20 22 34 36 36 20 39 33 27 340", "466 93
1b70: 38 22 2c 20 22 35 39 38 20 36 30 31 22 7d 3b 0d 8", "598 601"};.
1b80: 0a 09 20 20 76 65 63 74 6f 72 20 3c 73 74 72 69 .. vector <stri
1b90: 6e 67 3e 20 73 74 61 72 73 28 73 74 61 72 73 5f ng> stars(stars_
1ba0: 2c 20 73 74 61 72 73 5f 2b 73 69 7a 65 6f 66 28 , stars_+sizeof(
1bb0: 73 74 61 72 73 5f 29 2f 73 69 7a 65 6f 66 28 2a stars_)/sizeof(*
1bc0: 73 74 61 72 73 5f 29 29 3b 20 0d 0a 09 73 74 72 stars_)); ...str
1bd0: 69 6e 67 20 73 68 69 70 73 5f 5b 5d 20 3d 20 7b ing ships_[] = {
1be0: 22 34 31 30 20 39 35 31 20 34 37 32 20 31 30 30 "410 951 472 100
1bf0: 20 33 33 37 20 32 32 36 20 32 31 30 22 2c 20 22 337 226 210", "
1c00: 37 31 33 20 33 35 32 20 36 37 37 20 39 30 38 20 713 352 677 908
1c10: 37 33 31 20 36 38 37 20 33 30 30 22 2c 0d 0a 20 731 687 300",..
1c20: 22 31 39 31 20 34 31 20 33 33 37 20 39 32 20 34 "191 41 337 92 4
1c30: 34 36 20 37 31 36 20 32 31 33 22 2c 20 22 35 39 46 716 213", "59
1c40: 38 20 38 38 39 20 34 34 36 20 39 30 37 20 31 34 8 889 446 907 14
1c50: 38 20 36 35 30 20 32 30 33 22 2c 0d 0a 20 22 31 8 650 203",.. "1
1c60: 36 38 20 35 35 36 20 34 37 30 20 39 32 34 20 33 68 556 470 924 3
1c70: 34 34 20 33 36 39 20 31 39 38 22 2c 20 22 33 30 44 369 198", "30
1c80: 30 20 31 38 32 20 33 35 30 20 39 33 36 20 37 33 0 182 350 936 73
1c90: 37 20 35 33 33 20 34 35 22 2c 0d 0a 20 22 34 31 7 533 45",.. "41
1ca0: 30 20 38 37 31 20 34 38 38 20 37 30 33 20 37 34 0 871 488 703 74
1cb0: 36 20 36 33 31 20 38 30 22 2c 20 22 32 37 30 20 6 631 80", "270
1cc0: 37 37 37 20 36 33 36 20 35 33 39 20 31 37 32 20 777 636 539 172
1cd0: 31 30 33 20 35 36 22 2c 0d 0a 20 22 34 36 36 20 103 56",.. "466
1ce0: 39 30 36 20 35 32 32 20 39 38 20 36 39 33 20 37 906 522 98 693 7
1cf0: 37 20 33 30 39 22 2c 20 22 37 36 38 20 36 39 38 7 309", "768 698
1d00: 20 38 34 36 20 31 31 30 20 31 34 20 36 34 33 20 846 110 14 643
1d10: 31 34 22 2c 0d 0a 20 22 37 35 35 20 37 32 34 20 14",.. "755 724
1d20: 36 36 34 20 34 36 35 20 32 36 33 20 37 35 39 20 664 465 263 759
1d30: 31 32 30 22 7d 3b 0d 0a 09 20 20 76 65 63 74 6f 120"};... vecto
1d40: 72 20 3c 73 74 72 69 6e 67 3e 20 73 68 69 70 73 r <string> ships
1d50: 28 73 68 69 70 73 5f 2c 20 73 68 69 70 73 5f 2b (ships_, ships_+
1d60: 73 69 7a 65 6f 66 28 73 68 69 70 73 5f 29 2f 73 sizeof(ships_)/s
1d70: 69 7a 65 6f 66 28 2a 73 68 69 70 73 5f 29 29 3b izeof(*ships_));
1d80: 20 0d 0a 09 4c 44 20 5f 20 3d 20 33 31 2e 39 36 ...LD _ = 31.96
1d90: 35 37 37 30 39 35 36 33 31 36 33 36 32 3b 20 0d 5770956316362; .
1da0: 0a 45 4e 44 0d 0a 43 41 53 45 28 34 29 0d 0a 09 .END..CASE(4)...
1db0: 73 74 72 69 6e 67 20 73 74 61 72 73 5f 5b 5d 20 string stars_[]
1dc0: 3d 20 0d 0a 7b 22 32 30 20 31 22 2c 20 22 37 30 = ..{"20 1", "70
1dd0: 20 31 22 2c 20 22 31 32 30 20 31 22 2c 20 22 31 1", "120 1", "1
1de0: 37 30 20 31 22 2c 20 22 32 32 30 20 31 22 2c 20 70 1", "220 1",
1df0: 22 32 37 30 20 31 22 2c 20 22 33 32 30 20 31 22 "270 1", "320 1"
1e00: 2c 20 22 33 37 30 20 31 22 2c 20 22 34 32 30 20 , "370 1", "420
1e10: 31 22 2c 20 22 34 37 30 20 31 22 2c 20 22 35 32 1", "470 1", "52
1e20: 30 20 31 22 2c 20 22 35 37 30 20 31 22 2c 20 22 0 1", "570 1", "
1e30: 36 32 30 20 31 22 2c 20 22 36 37 30 20 31 22 2c 620 1", "670 1",
1e40: 20 22 37 32 30 20 31 22 2c 20 22 37 37 30 20 31 "720 1", "770 1
1e50: 22 2c 20 22 38 32 30 20 31 22 2c 20 22 38 37 30 ", "820 1", "870
1e60: 20 31 22 2c 20 22 39 32 30 20 31 22 2c 20 22 39 1", "920 1", "9
1e70: 37 30 20 31 22 7d 0d 0a 3b 0d 0a 09 20 20 76 65 70 1"}..;... ve
1e80: 63 74 6f 72 20 3c 73 74 72 69 6e 67 3e 20 73 74 ctor <string> st
1e90: 61 72 73 28 73 74 61 72 73 5f 2c 20 73 74 61 72 ars(stars_, star
1ea0: 73 5f 2b 73 69 7a 65 6f 66 28 73 74 61 72 73 5f s_+sizeof(stars_
1eb0: 29 2f 73 69 7a 65 6f 66 28 2a 73 74 61 72 73 5f )/sizeof(*stars_
1ec0: 29 29 3b 20 0d 0a 09 73 74 72 69 6e 67 20 73 68 )); ...string sh
1ed0: 69 70 73 5f 5b 5d 20 3d 0d 0a 09 09 7b 22 31 20 ips_[] =....{"1
1ee0: 32 31 20 31 30 30 30 20 32 31 20 31 20 32 31 20 21 1000 21 1 21
1ef0: 32 35 37 22 2c 20 22 31 20 32 30 20 31 30 30 30 257", "1 20 1000
1f00: 20 32 30 20 31 20 32 31 20 31 30 32 22 2c 20 22 20 1 21 102", "
1f10: 31 20 31 39 20 31 30 30 30 20 31 39 20 31 20 32 1 19 1000 19 1 2
1f20: 31 20 37 35 22 2c 20 22 31 20 31 38 20 31 30 30 1 75", "1 18 100
1f30: 30 20 31 38 20 31 20 32 31 20 36 31 22 2c 20 22 0 18 1 21 61", "
1f40: 31 20 31 37 20 31 30 30 30 20 31 37 20 31 20 32 1 17 1000 17 1 2
1f50: 31 20 35 31 22 2c 20 22 31 20 31 36 20 31 30 30 1 51", "1 16 100
1f60: 30 20 31 36 20 31 20 32 31 20 34 34 22 2c 20 22 0 16 1 21 44", "
1f70: 31 20 31 35 20 31 30 30 30 20 31 35 20 31 20 32 1 15 1000 15 1 2
1f80: 31 20 33 39 22 2c 20 22 31 20 31 34 20 31 30 30 1 39", "1 14 100
1f90: 30 20 31 34 20 31 20 32 31 20 33 34 22 2c 20 22 0 14 1 21 34", "
1fa0: 31 20 31 33 20 31 30 30 30 20 31 33 20 31 20 32 1 13 1000 13 1 2
1fb0: 31 20 33 30 22 2c 20 22 31 20 31 32 20 31 30 30 1 30", "1 12 100
1fc0: 30 20 31 32 20 31 20 32 31 20 32 37 22 2c 20 22 0 12 1 21 27", "
1fd0: 31 20 31 31 20 31 30 30 30 20 31 31 20 31 20 32 1 11 1000 11 1 2
1fe0: 31 20 32 34 22 2c 20 22 31 20 31 30 20 31 30 30 1 24", "1 10 100
1ff0: 30 20 31 30 20 31 20 32 31 20 32 31 22 2c 20 22 0 10 1 21 21", "
2000: 31 20 39 20 31 30 30 30 20 39 20 31 20 32 31 20 1 9 1000 9 1 21
2010: 31 38 22 2c 20 22 31 20 38 20 31 30 30 30 20 38 18", "1 8 1000 8
2020: 20 31 20 32 31 20 31 35 22 2c 20 22 31 20 37 20 1 21 15", "1 7
2030: 31 30 30 30 20 37 20 31 20 32 31 20 31 33 22 2c 1000 7 1 21 13",
2040: 20 22 31 20 36 20 31 30 30 30 20 36 20 31 20 32 "1 6 1000 6 1 2
2050: 31 20 31 31 22 2c 20 22 31 20 35 20 31 30 30 30 1 11", "1 5 1000
2060: 20 35 20 31 20 32 31 20 39 22 2c 20 22 31 20 34 5 1 21 9", "1 4
2070: 20 31 30 30 30 20 34 20 31 20 32 31 20 37 22 2c 1000 4 1 21 7",
2080: 20 22 31 20 33 20 31 30 30 30 20 33 20 31 20 32 "1 3 1000 3 1 2
2090: 31 20 35 22 2c 20 22 31 20 32 20 31 30 30 30 20 1 5", "1 2 1000
20a0: 32 20 31 20 32 31 20 33 22 7d 0d 0a 3b 0d 0a 09 2 1 21 3"}..;...
20b0: 20 20 76 65 63 74 6f 72 20 3c 73 74 72 69 6e 67 vector <string
20c0: 3e 20 73 68 69 70 73 28 73 68 69 70 73 5f 2c 20 > ships(ships_,
20d0: 73 68 69 70 73 5f 2b 73 69 7a 65 6f 66 28 73 68 ships_+sizeof(sh
20e0: 69 70 73 5f 29 2f 73 69 7a 65 6f 66 28 2a 73 68 ips_)/sizeof(*sh
20f0: 69 70 73 5f 29 29 3b 20 0d 0a 09 4c 44 20 5f 20 ips_)); ...LD _
2100: 3d 20 38 33 37 2e 30 37 30 39 30 31 35 37 32 37 = 837.0709015727
2110: 32 33 34 3b 20 0d 0a 45 4e 44 0d 0a 43 41 53 45 234; ..END..CASE
2120: 28 35 29 0d 0a 09 73 74 72 69 6e 67 20 73 74 61 (5)...string sta
2130: 72 73 5f 5b 5d 20 3d 20 7b 22 38 20 37 22 2c 20 rs_[] = {"8 7",
2140: 22 31 31 20 39 22 7d 3b 0d 0a 09 76 65 63 74 6f "11 9"};...vecto
2150: 72 20 3c 73 74 72 69 6e 67 3e 20 73 74 61 72 73 r <string> stars
2160: 28 73 74 61 72 73 5f 2c 20 73 74 61 72 73 5f 2b (stars_, stars_+
2170: 73 69 7a 65 6f 66 28 73 74 61 72 73 5f 29 2f 73 sizeof(stars_)/s
2180: 69 7a 65 6f 66 28 2a 73 74 61 72 73 5f 29 29 3b izeof(*stars_));
2190: 20 0d 0a 09 73 74 72 69 6e 67 20 73 68 69 70 73 ...string ships
21a0: 5f 5b 5d 20 3d 20 7b 22 31 31 20 31 34 20 38 20 _[] = {"11 14 8
21b0: 31 30 20 39 32 20 33 20 33 22 2c 20 22 31 32 20 10 92 3 3", "12
21c0: 31 34 20 31 32 20 36 20 34 33 34 20 34 20 36 22 14 12 6 434 4 6"
21d0: 7d 3b 0d 0a 09 20 20 76 65 63 74 6f 72 20 3c 73 };... vector <s
21e0: 74 72 69 6e 67 3e 20 73 68 69 70 73 28 73 68 69 tring> ships(shi
21f0: 70 73 5f 2c 20 73 68 69 70 73 5f 2b 73 69 7a 65 ps_, ships_+size
2200: 6f 66 28 73 68 69 70 73 5f 29 2f 73 69 7a 65 6f of(ships_)/sizeo
2210: 66 28 2a 73 68 69 70 73 5f 29 29 3b 20 0d 0a 09 f(*ships_)); ...
2220: 4c 44 20 5f 20 3d 20 30 2e 30 31 35 38 33 36 33 LD _ = 0.0158363
2230: 36 37 31 35 37 31 35 39 39 35 3b 20 0d 0a 45 4e 6715715995; ..EN
2240: 44 0d 0a 7d 0d 0a 2f 2f 20 45 4e 44 20 43 55 54 D..}..// END CUT
2250: 20 48 45 52 45 0d 0a HERE..