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 23 69 6e 63 6c 75 64 65 20 sert>..#include
0140: 3c 63 73 74 72 69 6e 67 3e 0d 0a 75 73 69 6e 67 <cstring>..using
0150: 20 6e 61 6d 65 73 70 61 63 65 20 73 74 64 3b 0d namespace std;.
0160: 0a 74 79 70 65 64 65 66 20 6c 6f 6e 67 20 6c 6f .typedef long lo
0170: 6e 67 20 4c 4c 3b 0d 0a 74 79 70 65 64 65 66 20 ng LL;..typedef
0180: 63 6f 6d 70 6c 65 78 3c 64 6f 75 62 6c 65 3e 20 complex<double>
0190: 43 4d 50 3b 0d 0a 0d 0a 73 74 61 74 69 63 20 63 CMP;....static c
01a0: 6f 6e 73 74 20 69 6e 74 20 4e 56 20 3d 20 35 31 onst int NV = 51
01b0: 32 3b 0d 0a 74 79 70 65 64 65 66 20 69 6e 74 20 2;..typedef int
01c0: 20 20 20 20 20 20 20 20 20 20 66 6c 6f 77 3b 0d flow;.
01d0: 0a 74 79 70 65 64 65 66 20 69 6e 74 20 20 20 20 .typedef int
01e0: 20 20 20 20 20 20 20 76 65 72 74 3b 0d 0a 74 79 vert;..ty
01f0: 70 65 64 65 66 20 76 65 72 74 20 20 20 20 20 20 pedef vert
0200: 20 20 20 20 65 64 67 65 3b 0d 0a 74 79 70 65 64 edge;..typed
0210: 65 66 20 76 65 63 74 6f 72 3c 65 64 67 65 3e 20 ef vector<edge>
0220: 20 65 64 67 65 73 3b 0d 0a 74 79 70 65 64 65 66 edges;..typedef
0230: 20 76 65 63 74 6f 72 3c 65 64 67 65 73 3e 20 67 vector<edges> g
0240: 72 61 70 68 3b 0d 0a 74 79 70 65 64 65 66 20 66 raph;..typedef f
0250: 6c 6f 77 20 20 20 20 20 20 20 20 20 20 66 6c 6f low flo
0260: 77 5f 67 72 61 70 68 5b 4e 56 5d 5b 4e 56 5d 3b w_graph[NV][NV];
0270: 0d 0a 73 74 61 74 69 63 20 63 6f 6e 73 74 20 66 ..static const f
0280: 6c 6f 77 20 49 4e 46 20 3d 20 30 78 33 66 66 66 low INF = 0x3fff
0290: 66 66 66 66 3b 0d 0a 0d 0a 66 6c 6f 77 20 64 69 ffff;....flow di
02a0: 6e 69 63 5f 64 66 73 28 20 67 72 61 70 68 26 20 nic_dfs( graph&
02b0: 47 2c 20 66 6c 6f 77 5f 67 72 61 70 68 20 46 2c G, flow_graph F,
02c0: 20 76 65 72 74 20 76 2c 20 76 65 72 74 20 44 2c vert v, vert D,
02d0: 0d 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 20 ..
02e0: 20 20 69 6e 74 20 4c 56 5b 5d 2c 20 66 6c 6f 77 int LV[], flow
02f0: 20 66 6c 6f 77 5f 69 6e 2c 20 69 6e 74 20 62 6c flow_in, int bl
0300: 6f 63 6b 65 64 5b 5d 20 29 0d 0a 7b 0d 0a 09 66 ocked[] )..{...f
0310: 6c 6f 77 20 66 6c 6f 77 5f 6f 75 74 20 3d 20 30 low flow_out = 0
0320: 3b 0d 0a 09 66 6f 72 28 69 6e 74 20 69 3d 30 3b ;...for(int i=0;
0330: 20 69 21 3d 47 5b 76 5d 2e 73 69 7a 65 28 29 3b i!=G[v].size();
0340: 20 2b 2b 69 29 20 7b 0d 0a 09 09 69 6e 74 20 75 ++i) {....int u
0350: 20 3d 20 47 5b 76 5d 5b 69 5d 3b 0d 0a 09 09 69 = G[v][i];....i
0360: 66 28 20 4c 56 5b 76 5d 2b 31 3d 3d 4c 56 5b 75 f( LV[v]+1==LV[u
0370: 5d 20 26 26 20 46 5b 76 5d 5b 75 5d 20 29 20 7b ] && F[v][u] ) {
0380: 0d 0a 09 09 09 66 6c 6f 77 20 66 20 3d 20 6d 69 .....flow f = mi
0390: 6e 28 66 6c 6f 77 5f 69 6e 2d 66 6c 6f 77 5f 6f n(flow_in-flow_o
03a0: 75 74 2c 20 46 5b 76 5d 5b 75 5d 29 3b 0d 0a 09 ut, F[v][u]);...
03b0: 09 09 69 66 28 20 75 3d 3d 44 20 7c 7c 20 21 62 ..if( u==D || !b
03c0: 6c 6f 63 6b 65 64 5b 75 5d 20 26 26 20 28 66 3d locked[u] && (f=
03d0: 64 69 6e 69 63 5f 64 66 73 28 47 2c 46 2c 75 2c dinic_dfs(G,F,u,
03e0: 44 2c 4c 56 2c 66 2c 62 6c 6f 63 6b 65 64 29 29 D,LV,f,blocked))
03f0: 20 29 20 7b 0d 0a 09 09 09 09 46 5b 76 5d 5b 75 ) {......F[v][u
0400: 5d 20 20 2d 3d 20 66 3b 0d 0a 09 09 09 09 46 5b ] -= f;......F[
0410: 75 5d 5b 76 5d 20 20 2b 3d 20 66 3b 0d 0a 09 09 u][v] += f;....
0420: 09 09 66 6c 6f 77 5f 6f 75 74 20 2b 3d 20 66 3b ..flow_out += f;
0430: 0d 0a 09 09 09 09 69 66 28 20 66 6c 6f 77 5f 69 ......if( flow_i
0440: 6e 20 3d 3d 20 66 6c 6f 77 5f 6f 75 74 20 29 20 n == flow_out )
0450: 72 65 74 75 72 6e 20 66 6c 6f 77 5f 6f 75 74 3b return flow_out;
0460: 0d 0a 09 09 09 7d 0d 0a 09 09 7d 0d 0a 09 7d 0d .....}....}...}.
0470: 0a 09 62 6c 6f 63 6b 65 64 5b 76 5d 20 3d 20 28 ..blocked[v] = (
0480: 66 6c 6f 77 5f 6f 75 74 3d 3d 30 29 3b 0d 0a 09 flow_out==0);...
0490: 72 65 74 75 72 6e 20 66 6c 6f 77 5f 6f 75 74 3b return flow_out;
04a0: 0d 0a 7d 0d 0a 0d 0a 66 6c 6f 77 20 6d 61 78 46 ..}....flow maxF
04b0: 6c 6f 77 28 20 67 72 61 70 68 26 20 47 2c 20 66 low( graph& G, f
04c0: 6c 6f 77 5f 67 72 61 70 68 20 46 2c 20 76 65 72 low_graph F, ver
04d0: 74 20 53 2c 20 76 65 72 74 20 44 20 29 0d 0a 7b t S, vert D )..{
04e0: 0d 0a 09 66 6f 72 28 20 66 6c 6f 77 20 74 6f 74 ...for( flow tot
04f0: 61 6c 3d 30 20 3b 3b 20 29 20 7b 0d 0a 09 09 69 al=0 ;; ) {....i
0500: 6e 74 20 4c 56 5b 4e 56 5d 20 3d 20 7b 30 7d 3b nt LV[NV] = {0};
0510: 0d 0a 09 09 76 65 63 74 6f 72 3c 69 6e 74 3e 20 ....vector<int>
0520: 51 28 31 2c 20 53 29 3b 0d 0a 09 09 66 6f 72 28 Q(1, S);....for(
0530: 69 6e 74 20 6c 76 3d 31 3b 20 21 51 2e 65 6d 70 int lv=1; !Q.emp
0540: 74 79 28 29 3b 20 2b 2b 6c 76 29 20 7b 0d 0a 09 ty(); ++lv) {...
0550: 09 09 76 65 63 74 6f 72 3c 69 6e 74 3e 20 51 32 ..vector<int> Q2
0560: 3b 0d 0a 09 09 09 66 6f 72 28 69 6e 74 20 69 3d ;.....for(int i=
0570: 30 3b 20 69 21 3d 51 2e 73 69 7a 65 28 29 3b 20 0; i!=Q.size();
0580: 2b 2b 69 29 20 7b 0d 0a 09 09 09 09 65 64 67 65 ++i) {......edge
0590: 73 26 20 6e 65 20 3d 20 47 5b 51 5b 69 5d 5d 3b s& ne = G[Q[i]];
05a0: 0d 0a 09 09 09 09 66 6f 72 28 69 6e 74 20 6a 3d ......for(int j=
05b0: 30 3b 20 6a 21 3d 6e 65 2e 73 69 7a 65 28 29 3b 0; j!=ne.size();
05c0: 20 2b 2b 6a 29 0d 0a 09 09 09 09 09 69 66 28 20 ++j).......if(
05d0: 46 5b 51 5b 69 5d 5d 5b 6e 65 5b 6a 5d 5d 20 26 F[Q[i]][ne[j]] &
05e0: 26 20 21 4c 56 5b 6e 65 5b 6a 5d 5d 20 26 26 20 & !LV[ne[j]] &&
05f0: 6e 65 5b 6a 5d 21 3d 53 20 29 0d 0a 09 09 09 09 ne[j]!=S )......
0600: 09 09 4c 56 5b 6e 65 5b 6a 5d 5d 3d 6c 76 2c 20 ..LV[ne[j]]=lv,
0610: 51 32 2e 70 75 73 68 5f 62 61 63 6b 28 6e 65 5b Q2.push_back(ne[
0620: 6a 5d 29 3b 0d 0a 09 09 09 7d 0d 0a 09 09 09 51 j]);.....}.....Q
0630: 2e 73 77 61 70 28 51 32 29 3b 0d 0a 09 09 7d 0d .swap(Q2);....}.
0640: 0a 0d 0a 09 09 69 66 28 20 21 4c 56 5b 44 5d 20 .....if( !LV[D]
0650: 29 0d 0a 09 09 09 72 65 74 75 72 6e 20 74 6f 74 ).....return tot
0660: 61 6c 3b 0d 0a 0d 0a 09 09 69 6e 74 20 62 6c 6f al;......int blo
0670: 63 6b 65 64 5b 4e 56 5d 20 3d 20 7b 7d 3b 0d 0a cked[NV] = {};..
0680: 09 09 74 6f 74 61 6c 20 2b 3d 20 64 69 6e 69 63 ..total += dinic
0690: 5f 64 66 73 28 20 47 2c 20 46 2c 20 53 2c 20 44 _dfs( G, F, S, D
06a0: 2c 20 4c 56 2c 20 30 78 37 66 66 66 66 66 66 66 , LV, 0x7fffffff
06b0: 2c 20 62 6c 6f 63 6b 65 64 20 29 3b 0d 0a 09 7d , blocked );...}
06c0: 0d 0a 7d 0d 0a 0d 0a 63 6c 61 73 73 20 47 72 65 ..}....class Gre
06d0: 65 6e 57 61 72 66 61 72 65 20 7b 20 70 75 62 6c enWarfare { publ
06e0: 69 63 3a 0d 0a 09 69 6e 74 20 6d 69 6e 69 6d 75 ic:...int minimu
06f0: 6d 45 6e 65 72 67 79 43 6f 73 74 28 76 65 63 74 mEnergyCost(vect
0700: 6f 72 20 3c 69 6e 74 3e 20 63 61 6e 6f 6e 58 2c or <int> canonX,
0710: 20 76 65 63 74 6f 72 20 3c 69 6e 74 3e 20 63 61 vector <int> ca
0720: 6e 6f 6e 59 2c 20 76 65 63 74 6f 72 20 3c 69 6e nonY, vector <in
0730: 74 3e 20 62 61 73 65 58 2c 20 76 65 63 74 6f 72 t> baseX, vector
0740: 20 3c 69 6e 74 3e 20 62 61 73 65 59 2c 20 76 65 <int> baseY, ve
0750: 63 74 6f 72 20 3c 69 6e 74 3e 20 70 6c 61 6e 74 ctor <int> plant
0760: 58 2c 20 76 65 63 74 6f 72 20 3c 69 6e 74 3e 20 X, vector <int>
0770: 70 6c 61 6e 74 59 2c 20 69 6e 74 20 65 6e 65 72 plantY, int ener
0780: 67 79 53 75 70 70 6c 79 52 61 64 69 75 73 29 20 gySupplyRadius)
0790: 0d 0a 09 7b 0d 0a 09 09 69 6e 74 20 42 20 3d 20 ...{....int B =
07a0: 62 61 73 65 58 2e 73 69 7a 65 28 29 3b 0d 0a 09 baseX.size();...
07b0: 09 69 6e 74 20 50 20 3d 20 70 6c 61 6e 74 58 2e .int P = plantX.
07c0: 73 69 7a 65 28 29 3b 0d 0a 0d 0a 09 09 67 72 61 size();......gra
07d0: 70 68 20 20 20 20 20 20 47 28 50 2b 50 2b 42 2b ph G(P+P+B+
07e0: 42 2b 32 29 3b 0d 0a 09 09 66 6c 6f 77 5f 67 72 B+2);....flow_gr
07f0: 61 70 68 20 46 20 3d 20 7b 7d 3b 0d 0a 0d 0a 09 aph F = {};.....
0800: 09 66 6f 72 28 69 6e 74 20 78 3d 30 3b 20 78 3c .for(int x=0; x<
0810: 50 3b 20 2b 2b 78 29 20 7b 0d 0a 09 09 09 47 5b P; ++x) {.....G[
0820: 50 2b 50 2b 42 2b 42 5d 2e 70 75 73 68 5f 62 61 P+P+B+B].push_ba
0830: 63 6b 28 78 29 3b 0d 0a 09 09 09 47 5b 78 5d 2e ck(x);.....G[x].
0840: 70 75 73 68 5f 62 61 63 6b 28 50 2b 50 2b 42 2b push_back(P+P+B+
0850: 42 29 3b 0d 0a 09 09 09 46 5b 50 2b 50 2b 42 2b B);.....F[P+P+B+
0860: 42 5d 5b 78 5d 20 3d 20 49 4e 46 3b 0d 0a 09 09 B][x] = INF;....
0870: 7d 0d 0a 09 09 66 6f 72 28 69 6e 74 20 78 3d 30 }....for(int x=0
0880: 3b 20 78 3c 50 3b 20 2b 2b 78 29 20 7b 0d 0a 09 ; x<P; ++x) {...
0890: 09 09 47 5b 78 5d 2e 70 75 73 68 5f 62 61 63 6b ..G[x].push_back
08a0: 28 50 2b 78 29 3b 0d 0a 09 09 09 47 5b 50 2b 78 (P+x);.....G[P+x
08b0: 5d 2e 70 75 73 68 5f 62 61 63 6b 28 78 29 3b 0d ].push_back(x);.
08c0: 0a 09 09 09 46 5b 78 5d 5b 50 2b 78 5d 20 3d 20 ....F[x][P+x] =
08d0: 62 72 65 61 6b 45 6e 65 72 67 79 28 63 61 6e 6f breakEnergy(cano
08e0: 6e 58 2c 20 63 61 6e 6f 6e 59 2c 20 70 6c 61 6e nX, canonY, plan
08f0: 74 58 5b 78 5d 2c 20 70 6c 61 6e 74 59 5b 78 5d tX[x], plantY[x]
0900: 29 3b 0d 0a 09 09 7d 0d 0a 09 09 66 6f 72 28 69 );....}....for(i
0910: 6e 74 20 78 3d 30 3b 20 78 3c 50 3b 20 2b 2b 78 nt x=0; x<P; ++x
0920: 29 0d 0a 09 09 09 66 6f 72 28 69 6e 74 20 79 3d ).....for(int y=
0930: 30 3b 20 79 3c 42 3b 20 2b 2b 79 29 0d 0a 09 09 0; y<B; ++y)....
0940: 09 09 69 66 28 20 64 69 73 74 28 70 6c 61 6e 74 ..if( dist(plant
0950: 58 5b 78 5d 2c 70 6c 61 6e 74 59 5b 78 5d 2c 62 X[x],plantY[x],b
0960: 61 73 65 58 5b 79 5d 2c 62 61 73 65 59 5b 79 5d aseX[y],baseY[y]
0970: 29 20 3c 3d 20 65 6e 65 72 67 79 53 75 70 70 6c ) <= energySuppl
0980: 79 52 61 64 69 75 73 2a 65 6e 65 72 67 79 53 75 yRadius*energySu
0990: 70 70 6c 79 52 61 64 69 75 73 20 29 20 7b 0d 0a pplyRadius ) {..
09a0: 09 09 09 09 09 47 5b 50 2b 78 5d 2e 70 75 73 68 .....G[P+x].push
09b0: 5f 62 61 63 6b 28 50 2b 50 2b 79 29 3b 0d 0a 09 _back(P+P+y);...
09c0: 09 09 09 09 47 5b 50 2b 50 2b 79 5d 2e 70 75 73 ....G[P+P+y].pus
09d0: 68 5f 62 61 63 6b 28 50 2b 78 29 3b 0d 0a 09 09 h_back(P+x);....
09e0: 09 09 09 46 5b 50 2b 78 5d 5b 50 2b 50 2b 79 5d ...F[P+x][P+P+y]
09f0: 20 3d 20 49 4e 46 3b 0d 0a 09 09 09 09 7d 0d 0a = INF;......}..
0a00: 09 09 66 6f 72 28 69 6e 74 20 78 3d 30 3b 20 78 ..for(int x=0; x
0a10: 3c 42 3b 20 2b 2b 78 29 20 7b 0d 0a 09 09 09 47 <B; ++x) {.....G
0a20: 5b 50 2b 50 2b 78 5d 2e 70 75 73 68 5f 62 61 63 [P+P+x].push_bac
0a30: 6b 28 50 2b 50 2b 42 2b 78 29 3b 0d 0a 09 09 09 k(P+P+B+x);.....
0a40: 47 5b 50 2b 50 2b 42 2b 78 5d 2e 70 75 73 68 5f G[P+P+B+x].push_
0a50: 62 61 63 6b 28 50 2b 50 2b 78 29 3b 0d 0a 09 09 back(P+P+x);....
0a60: 09 46 5b 50 2b 50 2b 78 5d 5b 50 2b 50 2b 42 2b .F[P+P+x][P+P+B+
0a70: 78 5d 20 3d 20 62 72 65 61 6b 45 6e 65 72 67 79 x] = breakEnergy
0a80: 28 63 61 6e 6f 6e 58 2c 20 63 61 6e 6f 6e 59 2c (canonX, canonY,
0a90: 20 62 61 73 65 58 5b 78 5d 2c 20 62 61 73 65 59 baseX[x], baseY
0aa0: 5b 78 5d 29 3b 0d 0a 09 09 7d 0d 0a 09 09 66 6f [x]);....}....fo
0ab0: 72 28 69 6e 74 20 78 3d 30 3b 20 78 3c 42 3b 20 r(int x=0; x<B;
0ac0: 2b 2b 78 29 20 7b 0d 0a 09 09 09 47 5b 50 2b 50 ++x) {.....G[P+P
0ad0: 2b 42 2b 78 5d 2e 70 75 73 68 5f 62 61 63 6b 28 +B+x].push_back(
0ae0: 50 2b 50 2b 42 2b 42 2b 31 29 3b 0d 0a 09 09 09 P+P+B+B+1);.....
0af0: 47 5b 50 2b 50 2b 42 2b 42 2b 31 5d 2e 70 75 73 G[P+P+B+B+1].pus
0b00: 68 5f 62 61 63 6b 28 50 2b 50 2b 42 2b 78 29 3b h_back(P+P+B+x);
0b10: 0d 0a 09 09 09 46 5b 50 2b 50 2b 42 2b 78 5d 5b .....F[P+P+B+x][
0b20: 50 2b 50 2b 42 2b 42 2b 31 5d 20 3d 20 49 4e 46 P+P+B+B+1] = INF
0b30: 3b 0d 0a 09 09 7d 0d 0a 0d 0a 09 09 72 65 74 75 ;....}......retu
0b40: 72 6e 20 6d 61 78 46 6c 6f 77 28 47 2c 20 46 2c rn maxFlow(G, F,
0b50: 20 50 2b 50 2b 42 2b 42 2c 20 50 2b 50 2b 42 2b P+P+B+B, P+P+B+
0b60: 42 2b 31 29 3b 0d 0a 09 7d 0d 0a 0d 0a 09 69 6e B+1);...}.....in
0b70: 74 20 64 69 73 74 28 69 6e 74 20 78 2c 20 69 6e t dist(int x, in
0b80: 74 20 79 2c 20 69 6e 74 20 58 2c 20 69 6e 74 20 t y, int X, int
0b90: 59 29 0d 0a 09 7b 0d 0a 09 09 72 65 74 75 72 6e Y)...{....return
0ba0: 20 28 58 2d 78 29 2a 28 58 2d 78 29 20 2b 20 28 (X-x)*(X-x) + (
0bb0: 59 2d 79 29 2a 28 59 2d 79 29 3b 0d 0a 09 7d 0d Y-y)*(Y-y);...}.
0bc0: 0a 0d 0a 09 69 6e 74 20 62 72 65 61 6b 45 6e 65 ....int breakEne
0bd0: 72 67 79 28 63 6f 6e 73 74 20 76 65 63 74 6f 72 rgy(const vector
0be0: 3c 69 6e 74 3e 26 20 63 78 2c 20 63 6f 6e 73 74 <int>& cx, const
0bf0: 20 76 65 63 74 6f 72 3c 69 6e 74 3e 26 20 63 79 vector<int>& cy
0c00: 2c 20 69 6e 74 20 78 2c 20 69 6e 74 20 79 29 0d , int x, int y).
0c10: 0a 09 7b 0d 0a 09 09 69 6e 74 20 65 20 3d 20 30 ..{....int e = 0
0c20: 78 37 66 66 66 66 66 66 66 3b 0d 0a 09 09 66 6f x7fffffff;....fo
0c30: 72 28 69 6e 74 20 69 3d 30 3b 20 69 3c 63 78 2e r(int i=0; i<cx.
0c40: 73 69 7a 65 28 29 3b 20 2b 2b 69 29 0d 0a 09 09 size(); ++i)....
0c50: 09 65 20 3d 20 6d 69 6e 28 65 2c 20 64 69 73 74 .e = min(e, dist
0c60: 28 78 2c 79 2c 63 78 5b 69 5d 2c 63 79 5b 69 5d (x,y,cx[i],cy[i]
0c70: 29 29 3b 0d 0a 09 09 72 65 74 75 72 6e 20 65 3b ));....return e;
0c80: 0d 0a 09 7d 0d 0a 7d 3b 0d 0a 0d 0a 2f 2f 20 42 ...}..};....// B
0c90: 45 47 49 4e 20 43 55 54 20 48 45 52 45 0d 0a 23 EGIN CUT HERE..#
0ca0: 69 6e 63 6c 75 64 65 20 3c 63 74 69 6d 65 3e 0d include <ctime>.
0cb0: 0a 64 6f 75 62 6c 65 20 73 74 61 72 74 5f 74 69 .double start_ti
0cc0: 6d 65 3b 20 73 74 72 69 6e 67 20 74 69 6d 65 72 me; string timer
0cd0: 28 29 0d 0a 20 7b 20 6f 73 74 72 69 6e 67 73 74 ().. { ostringst
0ce0: 72 65 61 6d 20 6f 73 3b 20 6f 73 20 3c 3c 20 22 ream os; os << "
0cf0: 20 28 22 20 3c 3c 20 69 6e 74 28 28 63 6c 6f 63 (" << int((cloc
0d00: 6b 28 29 2d 73 74 61 72 74 5f 74 69 6d 65 29 2f k()-start_time)/
0d10: 43 4c 4f 43 4b 53 5f 50 45 52 5f 53 45 43 2a 31 CLOCKS_PER_SEC*1
0d20: 30 30 30 29 20 3c 3c 20 22 20 6d 73 65 63 29 22 000) << " msec)"
0d30: 3b 20 72 65 74 75 72 6e 20 6f 73 2e 73 74 72 28 ; return os.str(
0d40: 29 3b 20 7d 0d 0a 74 65 6d 70 6c 61 74 65 3c 74 ); }..template<t
0d50: 79 70 65 6e 61 6d 65 20 54 3e 20 6f 73 74 72 65 ypename T> ostre
0d60: 61 6d 26 20 6f 70 65 72 61 74 6f 72 3c 3c 28 6f am& operator<<(o
0d70: 73 74 72 65 61 6d 26 20 6f 73 2c 20 63 6f 6e 73 stream& os, cons
0d80: 74 20 76 65 63 74 6f 72 3c 54 3e 26 20 76 29 0d t vector<T>& v).
0d90: 0a 20 7b 20 6f 73 20 3c 3c 20 22 7b 20 22 3b 0d . { os << "{ ";.
0da0: 0a 20 20 20 66 6f 72 28 74 79 70 65 6e 61 6d 65 . for(typename
0db0: 20 76 65 63 74 6f 72 3c 54 3e 3a 3a 63 6f 6e 73 vector<T>::cons
0dc0: 74 5f 69 74 65 72 61 74 6f 72 20 69 74 3d 76 2e t_iterator it=v.
0dd0: 62 65 67 69 6e 28 29 3b 20 69 74 21 3d 76 2e 65 begin(); it!=v.e
0de0: 6e 64 28 29 3b 20 2b 2b 69 74 29 0d 0a 20 20 20 nd(); ++it)..
0df0: 6f 73 20 3c 3c 20 27 5c 22 27 20 3c 3c 20 2a 69 os << '\"' << *i
0e00: 74 20 3c 3c 20 27 5c 22 27 20 3c 3c 20 28 69 74 t << '\"' << (it
0e10: 2b 31 3d 3d 76 2e 65 6e 64 28 29 20 3f 20 22 22 +1==v.end() ? ""
0e20: 20 3a 20 22 2c 20 22 29 3b 20 6f 73 20 3c 3c 20 : ", "); os <<
0e30: 22 20 7d 22 3b 20 72 65 74 75 72 6e 20 6f 73 3b " }"; return os;
0e40: 20 7d 0d 0a 76 6f 69 64 20 76 65 72 69 66 79 5f }..void verify_
0e50: 63 61 73 65 28 63 6f 6e 73 74 20 69 6e 74 26 20 case(const int&
0e60: 45 78 70 65 63 74 65 64 2c 20 63 6f 6e 73 74 20 Expected, const
0e70: 69 6e 74 26 20 52 65 63 65 69 76 65 64 29 20 7b int& Received) {
0e80: 0d 0a 20 62 6f 6f 6c 20 6f 6b 20 3d 20 28 45 78 .. bool ok = (Ex
0e90: 70 65 63 74 65 64 20 3d 3d 20 52 65 63 65 69 76 pected == Receiv
0ea0: 65 64 29 3b 0d 0a 20 69 66 28 6f 6b 29 20 63 65 ed);.. if(ok) ce
0eb0: 72 72 20 3c 3c 20 22 50 41 53 53 45 44 22 20 3c rr << "PASSED" <
0ec0: 3c 20 74 69 6d 65 72 28 29 20 3c 3c 20 65 6e 64 < timer() << end
0ed0: 6c 3b 20 20 65 6c 73 65 20 7b 20 63 65 72 72 20 l; else { cerr
0ee0: 3c 3c 20 22 46 41 49 4c 45 44 22 20 3c 3c 20 74 << "FAILED" << t
0ef0: 69 6d 65 72 28 29 20 3c 3c 20 65 6e 64 6c 3b 0d imer() << endl;.
0f00: 0a 20 63 65 72 72 20 3c 3c 20 22 5c 74 6f 3a 20 . cerr << "\to:
0f10: 5c 22 22 20 3c 3c 20 45 78 70 65 63 74 65 64 20 \"" << Expected
0f20: 3c 3c 20 27 5c 22 27 20 3c 3c 20 65 6e 64 6c 20 << '\"' << endl
0f30: 3c 3c 20 22 5c 74 78 3a 20 5c 22 22 20 3c 3c 20 << "\tx: \"" <<
0f40: 52 65 63 65 69 76 65 64 20 3c 3c 20 27 5c 22 27 Received << '\"'
0f50: 20 3c 3c 20 65 6e 64 6c 3b 20 7d 20 7d 0d 0a 23 << endl; } }..#
0f60: 64 65 66 69 6e 65 20 43 41 53 45 28 4e 29 20 7b define CASE(N) {
0f70: 63 65 72 72 20 3c 3c 20 22 54 65 73 74 20 43 61 cerr << "Test Ca
0f80: 73 65 20 23 22 20 3c 3c 20 4e 20 3c 3c 20 22 2e se #" << N << ".
0f90: 2e 2e 22 20 3c 3c 20 66 6c 75 73 68 3b 20 73 74 .." << flush; st
0fa0: 61 72 74 5f 74 69 6d 65 3d 63 6c 6f 63 6b 28 29 art_time=clock()
0fb0: 3b 0d 0a 23 64 65 66 69 6e 65 20 45 4e 44 09 20 ;..#define END.
0fc0: 76 65 72 69 66 79 5f 63 61 73 65 28 5f 2c 20 47 verify_case(_, G
0fd0: 72 65 65 6e 57 61 72 66 61 72 65 28 29 2e 6d 69 reenWarfare().mi
0fe0: 6e 69 6d 75 6d 45 6e 65 72 67 79 43 6f 73 74 28 nimumEnergyCost(
0ff0: 63 61 6e 6f 6e 58 2c 20 63 61 6e 6f 6e 59 2c 20 canonX, canonY,
1000: 62 61 73 65 58 2c 20 62 61 73 65 59 2c 20 70 6c baseX, baseY, pl
1010: 61 6e 74 58 2c 20 70 6c 61 6e 74 59 2c 20 65 6e antX, plantY, en
1020: 65 72 67 79 53 75 70 70 6c 79 52 61 64 69 75 73 ergySupplyRadius
1030: 29 29 3b 7d 0d 0a 69 6e 74 20 6d 61 69 6e 28 29 ));}..int main()
1040: 7b 0d 0a 0d 0a 43 41 53 45 28 30 29 0d 0a 09 69 {....CASE(0)...i
1050: 6e 74 20 63 61 6e 6f 6e 58 5f 5b 5d 20 3d 20 7b nt canonX_[] = {
1060: 20 30 20 7d 3b 0d 0a 09 20 20 76 65 63 74 6f 72 0 };... vector
1070: 20 3c 69 6e 74 3e 20 63 61 6e 6f 6e 58 28 63 61 <int> canonX(ca
1080: 6e 6f 6e 58 5f 2c 20 63 61 6e 6f 6e 58 5f 2b 73 nonX_, canonX_+s
1090: 69 7a 65 6f 66 28 63 61 6e 6f 6e 58 5f 29 2f 73 izeof(canonX_)/s
10a0: 69 7a 65 6f 66 28 2a 63 61 6e 6f 6e 58 5f 29 29 izeof(*canonX_))
10b0: 3b 20 0d 0a 09 69 6e 74 20 63 61 6e 6f 6e 59 5f ; ...int canonY_
10c0: 5b 5d 20 3d 20 7b 20 30 20 7d 3b 0d 0a 09 20 20 [] = { 0 };...
10d0: 76 65 63 74 6f 72 20 3c 69 6e 74 3e 20 63 61 6e vector <int> can
10e0: 6f 6e 59 28 63 61 6e 6f 6e 59 5f 2c 20 63 61 6e onY(canonY_, can
10f0: 6f 6e 59 5f 2b 73 69 7a 65 6f 66 28 63 61 6e 6f onY_+sizeof(cano
1100: 6e 59 5f 29 2f 73 69 7a 65 6f 66 28 2a 63 61 6e nY_)/sizeof(*can
1110: 6f 6e 59 5f 29 29 3b 20 0d 0a 09 69 6e 74 20 62 onY_)); ...int b
1120: 61 73 65 58 5f 5b 5d 20 3d 20 7b 31 2c 32 2c 33 aseX_[] = {1,2,3
1130: 7d 3b 0d 0a 09 20 20 76 65 63 74 6f 72 20 3c 69 };... vector <i
1140: 6e 74 3e 20 62 61 73 65 58 28 62 61 73 65 58 5f nt> baseX(baseX_
1150: 2c 20 62 61 73 65 58 5f 2b 73 69 7a 65 6f 66 28 , baseX_+sizeof(
1160: 62 61 73 65 58 5f 29 2f 73 69 7a 65 6f 66 28 2a baseX_)/sizeof(*
1170: 62 61 73 65 58 5f 29 29 3b 20 0d 0a 09 69 6e 74 baseX_)); ...int
1180: 20 62 61 73 65 59 5f 5b 5d 20 3d 20 7b 30 2c 30 baseY_[] = {0,0
1190: 2c 30 7d 3b 0d 0a 09 20 20 76 65 63 74 6f 72 20 ,0};... vector
11a0: 3c 69 6e 74 3e 20 62 61 73 65 59 28 62 61 73 65 <int> baseY(base
11b0: 59 5f 2c 20 62 61 73 65 59 5f 2b 73 69 7a 65 6f Y_, baseY_+sizeo
11c0: 66 28 62 61 73 65 59 5f 29 2f 73 69 7a 65 6f 66 f(baseY_)/sizeof
11d0: 28 2a 62 61 73 65 59 5f 29 29 3b 20 0d 0a 09 69 (*baseY_)); ...i
11e0: 6e 74 20 70 6c 61 6e 74 58 5f 5b 5d 20 3d 20 7b nt plantX_[] = {
11f0: 33 7d 3b 0d 0a 09 20 20 76 65 63 74 6f 72 20 3c 3};... vector <
1200: 69 6e 74 3e 20 70 6c 61 6e 74 58 28 70 6c 61 6e int> plantX(plan
1210: 74 58 5f 2c 20 70 6c 61 6e 74 58 5f 2b 73 69 7a tX_, plantX_+siz
1220: 65 6f 66 28 70 6c 61 6e 74 58 5f 29 2f 73 69 7a eof(plantX_)/siz
1230: 65 6f 66 28 2a 70 6c 61 6e 74 58 5f 29 29 3b 20 eof(*plantX_));
1240: 0d 0a 09 69 6e 74 20 70 6c 61 6e 74 59 5f 5b 5d ...int plantY_[]
1250: 20 3d 20 7b 33 7d 3b 0d 0a 09 20 20 76 65 63 74 = {3};... vect
1260: 6f 72 20 3c 69 6e 74 3e 20 70 6c 61 6e 74 59 28 or <int> plantY(
1270: 70 6c 61 6e 74 59 5f 2c 20 70 6c 61 6e 74 59 5f plantY_, plantY_
1280: 2b 73 69 7a 65 6f 66 28 70 6c 61 6e 74 59 5f 29 +sizeof(plantY_)
1290: 2f 73 69 7a 65 6f 66 28 2a 70 6c 61 6e 74 59 5f /sizeof(*plantY_
12a0: 29 29 3b 20 0d 0a 09 69 6e 74 20 65 6e 65 72 67 )); ...int energ
12b0: 79 53 75 70 70 6c 79 52 61 64 69 75 73 20 3d 20 ySupplyRadius =
12c0: 34 3b 20 0d 0a 09 69 6e 74 20 5f 20 3d 20 31 34 4; ...int _ = 14
12d0: 3b 20 0d 0a 45 4e 44 0d 0a 43 41 53 45 28 31 29 ; ..END..CASE(1)
12e0: 0d 0a 09 69 6e 74 20 63 61 6e 6f 6e 58 5f 5b 5d ...int canonX_[]
12f0: 20 3d 20 7b 20 30 20 7d 3b 0d 0a 09 20 20 76 65 = { 0 };... ve
1300: 63 74 6f 72 20 3c 69 6e 74 3e 20 63 61 6e 6f 6e ctor <int> canon
1310: 58 28 63 61 6e 6f 6e 58 5f 2c 20 63 61 6e 6f 6e X(canonX_, canon
1320: 58 5f 2b 73 69 7a 65 6f 66 28 63 61 6e 6f 6e 58 X_+sizeof(canonX
1330: 5f 29 2f 73 69 7a 65 6f 66 28 2a 63 61 6e 6f 6e _)/sizeof(*canon
1340: 58 5f 29 29 3b 20 0d 0a 09 69 6e 74 20 63 61 6e X_)); ...int can
1350: 6f 6e 59 5f 5b 5d 20 3d 20 7b 20 30 20 7d 3b 0d onY_[] = { 0 };.
1360: 0a 09 20 20 76 65 63 74 6f 72 20 3c 69 6e 74 3e .. vector <int>
1370: 20 63 61 6e 6f 6e 59 28 63 61 6e 6f 6e 59 5f 2c canonY(canonY_,
1380: 20 63 61 6e 6f 6e 59 5f 2b 73 69 7a 65 6f 66 28 canonY_+sizeof(
1390: 63 61 6e 6f 6e 59 5f 29 2f 73 69 7a 65 6f 66 28 canonY_)/sizeof(
13a0: 2a 63 61 6e 6f 6e 59 5f 29 29 3b 20 0d 0a 09 69 *canonY_)); ...i
13b0: 6e 74 20 62 61 73 65 58 5f 5b 5d 20 3d 20 7b 31 nt baseX_[] = {1
13c0: 2c 32 2c 33 7d 3b 0d 0a 09 20 20 76 65 63 74 6f ,2,3};... vecto
13d0: 72 20 3c 69 6e 74 3e 20 62 61 73 65 58 28 62 61 r <int> baseX(ba
13e0: 73 65 58 5f 2c 20 62 61 73 65 58 5f 2b 73 69 7a seX_, baseX_+siz
13f0: 65 6f 66 28 62 61 73 65 58 5f 29 2f 73 69 7a 65 eof(baseX_)/size
1400: 6f 66 28 2a 62 61 73 65 58 5f 29 29 3b 20 0d 0a of(*baseX_)); ..
1410: 09 69 6e 74 20 62 61 73 65 59 5f 5b 5d 20 3d 20 .int baseY_[] =
1420: 7b 30 2c 30 2c 30 7d 3b 0d 0a 09 20 20 76 65 63 {0,0,0};... vec
1430: 74 6f 72 20 3c 69 6e 74 3e 20 62 61 73 65 59 28 tor <int> baseY(
1440: 62 61 73 65 59 5f 2c 20 62 61 73 65 59 5f 2b 73 baseY_, baseY_+s
1450: 69 7a 65 6f 66 28 62 61 73 65 59 5f 29 2f 73 69 izeof(baseY_)/si
1460: 7a 65 6f 66 28 2a 62 61 73 65 59 5f 29 29 3b 20 zeof(*baseY_));
1470: 0d 0a 09 69 6e 74 20 70 6c 61 6e 74 58 5f 5b 5d ...int plantX_[]
1480: 20 3d 20 7b 32 7d 3b 0d 0a 09 20 20 76 65 63 74 = {2};... vect
1490: 6f 72 20 3c 69 6e 74 3e 20 70 6c 61 6e 74 58 28 or <int> plantX(
14a0: 70 6c 61 6e 74 58 5f 2c 20 70 6c 61 6e 74 58 5f plantX_, plantX_
14b0: 2b 73 69 7a 65 6f 66 28 70 6c 61 6e 74 58 5f 29 +sizeof(plantX_)
14c0: 2f 73 69 7a 65 6f 66 28 2a 70 6c 61 6e 74 58 5f /sizeof(*plantX_
14d0: 29 29 3b 20 0d 0a 09 69 6e 74 20 70 6c 61 6e 74 )); ...int plant
14e0: 59 5f 5b 5d 20 3d 20 7b 32 7d 3b 0d 0a 09 20 20 Y_[] = {2};...
14f0: 76 65 63 74 6f 72 20 3c 69 6e 74 3e 20 70 6c 61 vector <int> pla
1500: 6e 74 59 28 70 6c 61 6e 74 59 5f 2c 20 70 6c 61 ntY(plantY_, pla
1510: 6e 74 59 5f 2b 73 69 7a 65 6f 66 28 70 6c 61 6e ntY_+sizeof(plan
1520: 74 59 5f 29 2f 73 69 7a 65 6f 66 28 2a 70 6c 61 tY_)/sizeof(*pla
1530: 6e 74 59 5f 29 29 3b 20 0d 0a 09 69 6e 74 20 65 ntY_)); ...int e
1540: 6e 65 72 67 79 53 75 70 70 6c 79 52 61 64 69 75 nergySupplyRadiu
1550: 73 20 3d 20 34 3b 20 0d 0a 09 69 6e 74 20 5f 20 s = 4; ...int _
1560: 3d 20 38 3b 20 0d 0a 45 4e 44 0d 0a 43 41 53 45 = 8; ..END..CASE
1570: 28 32 29 0d 0a 09 69 6e 74 20 63 61 6e 6f 6e 58 (2)...int canonX
1580: 5f 5b 5d 20 3d 20 7b 33 2c 36 7d 3b 0d 0a 09 20 _[] = {3,6};...
1590: 20 76 65 63 74 6f 72 20 3c 69 6e 74 3e 20 63 61 vector <int> ca
15a0: 6e 6f 6e 58 28 63 61 6e 6f 6e 58 5f 2c 20 63 61 nonX(canonX_, ca
15b0: 6e 6f 6e 58 5f 2b 73 69 7a 65 6f 66 28 63 61 6e nonX_+sizeof(can
15c0: 6f 6e 58 5f 29 2f 73 69 7a 65 6f 66 28 2a 63 61 onX_)/sizeof(*ca
15d0: 6e 6f 6e 58 5f 29 29 3b 20 0d 0a 09 69 6e 74 20 nonX_)); ...int
15e0: 63 61 6e 6f 6e 59 5f 5b 5d 20 3d 20 7b 33 2c 36 canonY_[] = {3,6
15f0: 7d 3b 0d 0a 09 20 20 76 65 63 74 6f 72 20 3c 69 };... vector <i
1600: 6e 74 3e 20 63 61 6e 6f 6e 59 28 63 61 6e 6f 6e nt> canonY(canon
1610: 59 5f 2c 20 63 61 6e 6f 6e 59 5f 2b 73 69 7a 65 Y_, canonY_+size
1620: 6f 66 28 63 61 6e 6f 6e 59 5f 29 2f 73 69 7a 65 of(canonY_)/size
1630: 6f 66 28 2a 63 61 6e 6f 6e 59 5f 29 29 3b 20 0d of(*canonY_)); .
1640: 0a 09 69 6e 74 20 62 61 73 65 58 5f 5b 5d 20 3d ..int baseX_[] =
1650: 20 7b 31 2c 32 2c 33 2c 34 2c 35 7d 3b 0d 0a 09 {1,2,3,4,5};...
1660: 20 20 76 65 63 74 6f 72 20 3c 69 6e 74 3e 20 62 vector <int> b
1670: 61 73 65 58 28 62 61 73 65 58 5f 2c 20 62 61 73 aseX(baseX_, bas
1680: 65 58 5f 2b 73 69 7a 65 6f 66 28 62 61 73 65 58 eX_+sizeof(baseX
1690: 5f 29 2f 73 69 7a 65 6f 66 28 2a 62 61 73 65 58 _)/sizeof(*baseX
16a0: 5f 29 29 3b 20 0d 0a 09 69 6e 74 20 62 61 73 65 _)); ...int base
16b0: 59 5f 5b 5d 20 3d 20 7b 35 2c 34 2c 32 2c 33 2c Y_[] = {5,4,2,3,
16c0: 31 7d 3b 0d 0a 09 20 20 76 65 63 74 6f 72 20 3c 1};... vector <
16d0: 69 6e 74 3e 20 62 61 73 65 59 28 62 61 73 65 59 int> baseY(baseY
16e0: 5f 2c 20 62 61 73 65 59 5f 2b 73 69 7a 65 6f 66 _, baseY_+sizeof
16f0: 28 62 61 73 65 59 5f 29 2f 73 69 7a 65 6f 66 28 (baseY_)/sizeof(
1700: 2a 62 61 73 65 59 5f 29 29 3b 20 0d 0a 09 69 6e *baseY_)); ...in
1710: 74 20 70 6c 61 6e 74 58 5f 5b 5d 20 3d 20 7b 31 t plantX_[] = {1
1720: 2c 32 2c 35 7d 3b 0d 0a 09 20 20 76 65 63 74 6f ,2,5};... vecto
1730: 72 20 3c 69 6e 74 3e 20 70 6c 61 6e 74 58 28 70 r <int> plantX(p
1740: 6c 61 6e 74 58 5f 2c 20 70 6c 61 6e 74 58 5f 2b lantX_, plantX_+
1750: 73 69 7a 65 6f 66 28 70 6c 61 6e 74 58 5f 29 2f sizeof(plantX_)/
1760: 73 69 7a 65 6f 66 28 2a 70 6c 61 6e 74 58 5f 29 sizeof(*plantX_)
1770: 29 3b 20 0d 0a 09 69 6e 74 20 70 6c 61 6e 74 59 ); ...int plantY
1780: 5f 5b 5d 20 3d 20 7b 31 2c 32 2c 35 7d 3b 0d 0a _[] = {1,2,5};..
1790: 09 20 20 76 65 63 74 6f 72 20 3c 69 6e 74 3e 20 . vector <int>
17a0: 70 6c 61 6e 74 59 28 70 6c 61 6e 74 59 5f 2c 20 plantY(plantY_,
17b0: 70 6c 61 6e 74 59 5f 2b 73 69 7a 65 6f 66 28 70 plantY_+sizeof(p
17c0: 6c 61 6e 74 59 5f 29 2f 73 69 7a 65 6f 66 28 2a lantY_)/sizeof(*
17d0: 70 6c 61 6e 74 59 5f 29 29 3b 20 0d 0a 09 69 6e plantY_)); ...in
17e0: 74 20 65 6e 65 72 67 79 53 75 70 70 6c 79 52 61 t energySupplyRa
17f0: 64 69 75 73 20 3d 20 35 3b 20 0d 0a 09 69 6e 74 dius = 5; ...int
1800: 20 5f 20 3d 20 31 32 3b 20 0d 0a 45 4e 44 0d 0a _ = 12; ..END..
1810: 43 41 53 45 28 33 29 0d 0a 09 69 6e 74 20 63 61 CASE(3)...int ca
1820: 6e 6f 6e 58 5f 5b 5d 20 3d 20 7b 30 7d 3b 0d 0a nonX_[] = {0};..
1830: 09 20 20 76 65 63 74 6f 72 20 3c 69 6e 74 3e 20 . vector <int>
1840: 63 61 6e 6f 6e 58 28 63 61 6e 6f 6e 58 5f 2c 20 canonX(canonX_,
1850: 63 61 6e 6f 6e 58 5f 2b 73 69 7a 65 6f 66 28 63 canonX_+sizeof(c
1860: 61 6e 6f 6e 58 5f 29 2f 73 69 7a 65 6f 66 28 2a anonX_)/sizeof(*
1870: 63 61 6e 6f 6e 58 5f 29 29 3b 20 0d 0a 09 69 6e canonX_)); ...in
1880: 74 20 63 61 6e 6f 6e 59 5f 5b 5d 20 3d 20 7b 30 t canonY_[] = {0
1890: 7d 3b 0d 0a 09 20 20 76 65 63 74 6f 72 20 3c 69 };... vector <i
18a0: 6e 74 3e 20 63 61 6e 6f 6e 59 28 63 61 6e 6f 6e nt> canonY(canon
18b0: 59 5f 2c 20 63 61 6e 6f 6e 59 5f 2b 73 69 7a 65 Y_, canonY_+size
18c0: 6f 66 28 63 61 6e 6f 6e 59 5f 29 2f 73 69 7a 65 of(canonY_)/size
18d0: 6f 66 28 2a 63 61 6e 6f 6e 59 5f 29 29 3b 20 0d of(*canonY_)); .
18e0: 0a 09 69 6e 74 20 62 61 73 65 58 5f 5b 5d 20 3d ..int baseX_[] =
18f0: 20 7b 2d 31 30 2c 2d 31 30 2c 31 30 7d 3b 0d 0a {-10,-10,10};..
1900: 09 20 20 76 65 63 74 6f 72 20 3c 69 6e 74 3e 20 . vector <int>
1910: 62 61 73 65 58 28 62 61 73 65 58 5f 2c 20 62 61 baseX(baseX_, ba
1920: 73 65 58 5f 2b 73 69 7a 65 6f 66 28 62 61 73 65 seX_+sizeof(base
1930: 58 5f 29 2f 73 69 7a 65 6f 66 28 2a 62 61 73 65 X_)/sizeof(*base
1940: 58 5f 29 29 3b 20 0d 0a 09 69 6e 74 20 62 61 73 X_)); ...int bas
1950: 65 59 5f 5b 5d 20 3d 20 7b 31 30 2c 2d 31 30 2c eY_[] = {10,-10,
1960: 30 7d 3b 0d 0a 09 20 20 76 65 63 74 6f 72 20 3c 0};... vector <
1970: 69 6e 74 3e 20 62 61 73 65 59 28 62 61 73 65 59 int> baseY(baseY
1980: 5f 2c 20 62 61 73 65 59 5f 2b 73 69 7a 65 6f 66 _, baseY_+sizeof
1990: 28 62 61 73 65 59 5f 29 2f 73 69 7a 65 6f 66 28 (baseY_)/sizeof(
19a0: 2a 62 61 73 65 59 5f 29 29 3b 20 0d 0a 09 69 6e *baseY_)); ...in
19b0: 74 20 70 6c 61 6e 74 58 5f 5b 5d 20 3d 20 7b 31 t plantX_[] = {1
19c0: 30 2c 31 30 2c 2d 31 30 7d 3b 0d 0a 09 20 20 76 0,10,-10};... v
19d0: 65 63 74 6f 72 20 3c 69 6e 74 3e 20 70 6c 61 6e ector <int> plan
19e0: 74 58 28 70 6c 61 6e 74 58 5f 2c 20 70 6c 61 6e tX(plantX_, plan
19f0: 74 58 5f 2b 73 69 7a 65 6f 66 28 70 6c 61 6e 74 tX_+sizeof(plant
1a00: 58 5f 29 2f 73 69 7a 65 6f 66 28 2a 70 6c 61 6e X_)/sizeof(*plan
1a10: 74 58 5f 29 29 3b 20 0d 0a 09 69 6e 74 20 70 6c tX_)); ...int pl
1a20: 61 6e 74 59 5f 5b 5d 20 3d 20 7b 31 30 2c 2d 31 antY_[] = {10,-1
1a30: 30 2c 30 7d 3b 0d 0a 09 20 20 76 65 63 74 6f 72 0,0};... vector
1a40: 20 3c 69 6e 74 3e 20 70 6c 61 6e 74 59 28 70 6c <int> plantY(pl
1a50: 61 6e 74 59 5f 2c 20 70 6c 61 6e 74 59 5f 2b 73 antY_, plantY_+s
1a60: 69 7a 65 6f 66 28 70 6c 61 6e 74 59 5f 29 2f 73 izeof(plantY_)/s
1a70: 69 7a 65 6f 66 28 2a 70 6c 61 6e 74 59 5f 29 29 izeof(*plantY_))
1a80: 3b 20 0d 0a 09 69 6e 74 20 65 6e 65 72 67 79 53 ; ...int energyS
1a90: 75 70 70 6c 79 52 61 64 69 75 73 20 3d 20 31 30 upplyRadius = 10
1aa0: 3b 20 0d 0a 09 69 6e 74 20 5f 20 3d 20 32 30 30 ; ...int _ = 200
1ab0: 3b 20 0d 0a 45 4e 44 0d 0a 43 41 53 45 28 34 29 ; ..END..CASE(4)
1ac0: 0d 0a 09 69 6e 74 20 63 61 6e 6f 6e 58 5f 5b 5d ...int canonX_[]
1ad0: 20 3d 20 7b 30 7d 3b 0d 0a 09 20 20 76 65 63 74 = {0};... vect
1ae0: 6f 72 20 3c 69 6e 74 3e 20 63 61 6e 6f 6e 58 28 or <int> canonX(
1af0: 63 61 6e 6f 6e 58 5f 2c 20 63 61 6e 6f 6e 58 5f canonX_, canonX_
1b00: 2b 73 69 7a 65 6f 66 28 63 61 6e 6f 6e 58 5f 29 +sizeof(canonX_)
1b10: 2f 73 69 7a 65 6f 66 28 2a 63 61 6e 6f 6e 58 5f /sizeof(*canonX_
1b20: 29 29 3b 20 0d 0a 09 69 6e 74 20 63 61 6e 6f 6e )); ...int canon
1b30: 59 5f 5b 5d 20 3d 20 7b 30 7d 3b 0d 0a 09 20 20 Y_[] = {0};...
1b40: 76 65 63 74 6f 72 20 3c 69 6e 74 3e 20 63 61 6e vector <int> can
1b50: 6f 6e 59 28 63 61 6e 6f 6e 59 5f 2c 20 63 61 6e onY(canonY_, can
1b60: 6f 6e 59 5f 2b 73 69 7a 65 6f 66 28 63 61 6e 6f onY_+sizeof(cano
1b70: 6e 59 5f 29 2f 73 69 7a 65 6f 66 28 2a 63 61 6e nY_)/sizeof(*can
1b80: 6f 6e 59 5f 29 29 3b 20 0d 0a 09 69 6e 74 20 62 onY_)); ...int b
1b90: 61 73 65 58 5f 5b 5d 20 3d 20 7b 33 7d 3b 0d 0a aseX_[] = {3};..
1ba0: 09 20 20 76 65 63 74 6f 72 20 3c 69 6e 74 3e 20 . vector <int>
1bb0: 62 61 73 65 58 28 62 61 73 65 58 5f 2c 20 62 61 baseX(baseX_, ba
1bc0: 73 65 58 5f 2b 73 69 7a 65 6f 66 28 62 61 73 65 seX_+sizeof(base
1bd0: 58 5f 29 2f 73 69 7a 65 6f 66 28 2a 62 61 73 65 X_)/sizeof(*base
1be0: 58 5f 29 29 3b 20 0d 0a 09 69 6e 74 20 62 61 73 X_)); ...int bas
1bf0: 65 59 5f 5b 5d 20 3d 20 7b 33 7d 3b 0d 0a 09 20 eY_[] = {3};...
1c00: 20 76 65 63 74 6f 72 20 3c 69 6e 74 3e 20 62 61 vector <int> ba
1c10: 73 65 59 28 62 61 73 65 59 5f 2c 20 62 61 73 65 seY(baseY_, base
1c20: 59 5f 2b 73 69 7a 65 6f 66 28 62 61 73 65 59 5f Y_+sizeof(baseY_
1c30: 29 2f 73 69 7a 65 6f 66 28 2a 62 61 73 65 59 5f )/sizeof(*baseY_
1c40: 29 29 3b 20 0d 0a 09 69 6e 74 20 70 6c 61 6e 74 )); ...int plant
1c50: 58 5f 5b 5d 20 3d 20 7b 31 2c 32 2c 33 7d 3b 0d X_[] = {1,2,3};.
1c60: 0a 09 20 20 76 65 63 74 6f 72 20 3c 69 6e 74 3e .. vector <int>
1c70: 20 70 6c 61 6e 74 58 28 70 6c 61 6e 74 58 5f 2c plantX(plantX_,
1c80: 20 70 6c 61 6e 74 58 5f 2b 73 69 7a 65 6f 66 28 plantX_+sizeof(
1c90: 70 6c 61 6e 74 58 5f 29 2f 73 69 7a 65 6f 66 28 plantX_)/sizeof(
1ca0: 2a 70 6c 61 6e 74 58 5f 29 29 3b 20 0d 0a 09 69 *plantX_)); ...i
1cb0: 6e 74 20 70 6c 61 6e 74 59 5f 5b 5d 20 3d 20 7b nt plantY_[] = {
1cc0: 30 2c 30 2c 30 7d 3b 0d 0a 09 20 20 76 65 63 74 0,0,0};... vect
1cd0: 6f 72 20 3c 69 6e 74 3e 20 70 6c 61 6e 74 59 28 or <int> plantY(
1ce0: 70 6c 61 6e 74 59 5f 2c 20 70 6c 61 6e 74 59 5f plantY_, plantY_
1cf0: 2b 73 69 7a 65 6f 66 28 70 6c 61 6e 74 59 5f 29 +sizeof(plantY_)
1d00: 2f 73 69 7a 65 6f 66 28 2a 70 6c 61 6e 74 59 5f /sizeof(*plantY_
1d10: 29 29 3b 20 0d 0a 09 69 6e 74 20 65 6e 65 72 67 )); ...int energ
1d20: 79 53 75 70 70 6c 79 52 61 64 69 75 73 20 3d 20 ySupplyRadius =
1d30: 34 3b 20 0d 0a 09 69 6e 74 20 5f 20 3d 20 31 34 4; ...int _ = 14
1d40: 3b 20 0d 0a 45 4e 44 0d 0a 2f 2a 0d 0a 43 41 53 ; ..END../*..CAS
1d50: 45 28 35 29 0d 0a 09 69 6e 74 20 63 61 6e 6f 6e E(5)...int canon
1d60: 58 5f 5b 5d 20 3d 20 3b 0d 0a 09 20 20 76 65 63 X_[] = ;... vec
1d70: 74 6f 72 20 3c 69 6e 74 3e 20 63 61 6e 6f 6e 58 tor <int> canonX
1d80: 28 63 61 6e 6f 6e 58 5f 2c 20 63 61 6e 6f 6e 58 (canonX_, canonX
1d90: 5f 2b 73 69 7a 65 6f 66 28 63 61 6e 6f 6e 58 5f _+sizeof(canonX_
1da0: 29 2f 73 69 7a 65 6f 66 28 2a 63 61 6e 6f 6e 58 )/sizeof(*canonX
1db0: 5f 29 29 3b 20 0d 0a 09 69 6e 74 20 63 61 6e 6f _)); ...int cano
1dc0: 6e 59 5f 5b 5d 20 3d 20 3b 0d 0a 09 20 20 76 65 nY_[] = ;... ve
1dd0: 63 74 6f 72 20 3c 69 6e 74 3e 20 63 61 6e 6f 6e ctor <int> canon
1de0: 59 28 63 61 6e 6f 6e 59 5f 2c 20 63 61 6e 6f 6e Y(canonY_, canon
1df0: 59 5f 2b 73 69 7a 65 6f 66 28 63 61 6e 6f 6e 59 Y_+sizeof(canonY
1e00: 5f 29 2f 73 69 7a 65 6f 66 28 2a 63 61 6e 6f 6e _)/sizeof(*canon
1e10: 59 5f 29 29 3b 20 0d 0a 09 69 6e 74 20 62 61 73 Y_)); ...int bas
1e20: 65 58 5f 5b 5d 20 3d 20 3b 0d 0a 09 20 20 76 65 eX_[] = ;... ve
1e30: 63 74 6f 72 20 3c 69 6e 74 3e 20 62 61 73 65 58 ctor <int> baseX
1e40: 28 62 61 73 65 58 5f 2c 20 62 61 73 65 58 5f 2b (baseX_, baseX_+
1e50: 73 69 7a 65 6f 66 28 62 61 73 65 58 5f 29 2f 73 sizeof(baseX_)/s
1e60: 69 7a 65 6f 66 28 2a 62 61 73 65 58 5f 29 29 3b izeof(*baseX_));
1e70: 20 0d 0a 09 69 6e 74 20 62 61 73 65 59 5f 5b 5d ...int baseY_[]
1e80: 20 3d 20 3b 0d 0a 09 20 20 76 65 63 74 6f 72 20 = ;... vector
1e90: 3c 69 6e 74 3e 20 62 61 73 65 59 28 62 61 73 65 <int> baseY(base
1ea0: 59 5f 2c 20 62 61 73 65 59 5f 2b 73 69 7a 65 6f Y_, baseY_+sizeo
1eb0: 66 28 62 61 73 65 59 5f 29 2f 73 69 7a 65 6f 66 f(baseY_)/sizeof
1ec0: 28 2a 62 61 73 65 59 5f 29 29 3b 20 0d 0a 09 69 (*baseY_)); ...i
1ed0: 6e 74 20 70 6c 61 6e 74 58 5f 5b 5d 20 3d 20 3b nt plantX_[] = ;
1ee0: 0d 0a 09 20 20 76 65 63 74 6f 72 20 3c 69 6e 74 ... vector <int
1ef0: 3e 20 70 6c 61 6e 74 58 28 70 6c 61 6e 74 58 5f > plantX(plantX_
1f00: 2c 20 70 6c 61 6e 74 58 5f 2b 73 69 7a 65 6f 66 , plantX_+sizeof
1f10: 28 70 6c 61 6e 74 58 5f 29 2f 73 69 7a 65 6f 66 (plantX_)/sizeof
1f20: 28 2a 70 6c 61 6e 74 58 5f 29 29 3b 20 0d 0a 09 (*plantX_)); ...
1f30: 69 6e 74 20 70 6c 61 6e 74 59 5f 5b 5d 20 3d 20 int plantY_[] =
1f40: 3b 0d 0a 09 20 20 76 65 63 74 6f 72 20 3c 69 6e ;... vector <in
1f50: 74 3e 20 70 6c 61 6e 74 59 28 70 6c 61 6e 74 59 t> plantY(plantY
1f60: 5f 2c 20 70 6c 61 6e 74 59 5f 2b 73 69 7a 65 6f _, plantY_+sizeo
1f70: 66 28 70 6c 61 6e 74 59 5f 29 2f 73 69 7a 65 6f f(plantY_)/sizeo
1f80: 66 28 2a 70 6c 61 6e 74 59 5f 29 29 3b 20 0d 0a f(*plantY_)); ..
1f90: 09 69 6e 74 20 65 6e 65 72 67 79 53 75 70 70 6c .int energySuppl
1fa0: 79 52 61 64 69 75 73 20 3d 20 3b 20 0d 0a 09 69 yRadius = ; ...i
1fb0: 6e 74 20 5f 20 3d 20 3b 20 0d 0a 45 4e 44 0d 0a nt _ = ; ..END..
1fc0: 43 41 53 45 28 36 29 0d 0a 09 69 6e 74 20 63 61 CASE(6)...int ca
1fd0: 6e 6f 6e 58 5f 5b 5d 20 3d 20 3b 0d 0a 09 20 20 nonX_[] = ;...
1fe0: 76 65 63 74 6f 72 20 3c 69 6e 74 3e 20 63 61 6e vector <int> can
1ff0: 6f 6e 58 28 63 61 6e 6f 6e 58 5f 2c 20 63 61 6e onX(canonX_, can
2000: 6f 6e 58 5f 2b 73 69 7a 65 6f 66 28 63 61 6e 6f onX_+sizeof(cano
2010: 6e 58 5f 29 2f 73 69 7a 65 6f 66 28 2a 63 61 6e nX_)/sizeof(*can
2020: 6f 6e 58 5f 29 29 3b 20 0d 0a 09 69 6e 74 20 63 onX_)); ...int c
2030: 61 6e 6f 6e 59 5f 5b 5d 20 3d 20 3b 0d 0a 09 20 anonY_[] = ;...
2040: 20 76 65 63 74 6f 72 20 3c 69 6e 74 3e 20 63 61 vector <int> ca
2050: 6e 6f 6e 59 28 63 61 6e 6f 6e 59 5f 2c 20 63 61 nonY(canonY_, ca
2060: 6e 6f 6e 59 5f 2b 73 69 7a 65 6f 66 28 63 61 6e nonY_+sizeof(can
2070: 6f 6e 59 5f 29 2f 73 69 7a 65 6f 66 28 2a 63 61 onY_)/sizeof(*ca
2080: 6e 6f 6e 59 5f 29 29 3b 20 0d 0a 09 69 6e 74 20 nonY_)); ...int
2090: 62 61 73 65 58 5f 5b 5d 20 3d 20 3b 0d 0a 09 20 baseX_[] = ;...
20a0: 20 76 65 63 74 6f 72 20 3c 69 6e 74 3e 20 62 61 vector <int> ba
20b0: 73 65 58 28 62 61 73 65 58 5f 2c 20 62 61 73 65 seX(baseX_, base
20c0: 58 5f 2b 73 69 7a 65 6f 66 28 62 61 73 65 58 5f X_+sizeof(baseX_
20d0: 29 2f 73 69 7a 65 6f 66 28 2a 62 61 73 65 58 5f )/sizeof(*baseX_
20e0: 29 29 3b 20 0d 0a 09 69 6e 74 20 62 61 73 65 59 )); ...int baseY
20f0: 5f 5b 5d 20 3d 20 3b 0d 0a 09 20 20 76 65 63 74 _[] = ;... vect
2100: 6f 72 20 3c 69 6e 74 3e 20 62 61 73 65 59 28 62 or <int> baseY(b
2110: 61 73 65 59 5f 2c 20 62 61 73 65 59 5f 2b 73 69 aseY_, baseY_+si
2120: 7a 65 6f 66 28 62 61 73 65 59 5f 29 2f 73 69 7a zeof(baseY_)/siz
2130: 65 6f 66 28 2a 62 61 73 65 59 5f 29 29 3b 20 0d eof(*baseY_)); .
2140: 0a 09 69 6e 74 20 70 6c 61 6e 74 58 5f 5b 5d 20 ..int plantX_[]
2150: 3d 20 3b 0d 0a 09 20 20 76 65 63 74 6f 72 20 3c = ;... vector <
2160: 69 6e 74 3e 20 70 6c 61 6e 74 58 28 70 6c 61 6e int> plantX(plan
2170: 74 58 5f 2c 20 70 6c 61 6e 74 58 5f 2b 73 69 7a tX_, plantX_+siz
2180: 65 6f 66 28 70 6c 61 6e 74 58 5f 29 2f 73 69 7a eof(plantX_)/siz
2190: 65 6f 66 28 2a 70 6c 61 6e 74 58 5f 29 29 3b 20 eof(*plantX_));
21a0: 0d 0a 09 69 6e 74 20 70 6c 61 6e 74 59 5f 5b 5d ...int plantY_[]
21b0: 20 3d 20 3b 0d 0a 09 20 20 76 65 63 74 6f 72 20 = ;... vector
21c0: 3c 69 6e 74 3e 20 70 6c 61 6e 74 59 28 70 6c 61 <int> plantY(pla
21d0: 6e 74 59 5f 2c 20 70 6c 61 6e 74 59 5f 2b 73 69 ntY_, plantY_+si
21e0: 7a 65 6f 66 28 70 6c 61 6e 74 59 5f 29 2f 73 69 zeof(plantY_)/si
21f0: 7a 65 6f 66 28 2a 70 6c 61 6e 74 59 5f 29 29 3b zeof(*plantY_));
2200: 20 0d 0a 09 69 6e 74 20 65 6e 65 72 67 79 53 75 ...int energySu
2210: 70 70 6c 79 52 61 64 69 75 73 20 3d 20 3b 20 0d pplyRadius = ; .
2220: 0a 09 69 6e 74 20 5f 20 3d 20 3b 20 0d 0a 45 4e ..int _ = ; ..EN
2230: 44 0d 0a 2a 2f 0d 0a 7d 0d 0a 2f 2f 20 45 4e 44 D..*/..}..// END
2240: 20 43 55 54 20 48 45 52 45 0d 0a CUT HERE..