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 63 6c 61 73 73 20 43 6f CMP;....class Co
01a0: 6c 6f 72 66 75 6c 44 65 63 6f 72 61 74 69 6f 6e lorfulDecoration
01b0: 20 7b 20 70 75 62 6c 69 63 3a 0d 0a 09 69 6e 74 { public:...int
01c0: 20 67 65 74 4d 61 78 69 6d 75 6d 28 76 65 63 74 getMaximum(vect
01d0: 6f 72 20 3c 69 6e 74 3e 20 78 61 2c 20 76 65 63 or <int> xa, vec
01e0: 74 6f 72 20 3c 69 6e 74 3e 20 79 61 2c 20 76 65 tor <int> ya, ve
01f0: 63 74 6f 72 20 3c 69 6e 74 3e 20 78 62 2c 20 76 ctor <int> xb, v
0200: 65 63 74 6f 72 20 3c 69 6e 74 3e 20 79 62 29 20 ector <int> yb)
0210: 0d 0a 09 7b 0d 0a 09 09 69 6e 74 20 4c 3d 30 2c ...{....int L=0,
0220: 20 52 3d 31 30 30 30 30 30 30 30 30 31 3b 0d 0a R=1000000001;..
0230: 09 09 77 68 69 6c 65 28 20 52 2d 4c 3e 3d 32 20 ..while( R-L>=2
0240: 29 0d 0a 09 09 7b 0d 0a 09 09 09 69 6e 74 20 43 )....{.....int C
0250: 20 3d 20 28 4c 2b 52 29 2f 32 3b 0d 0a 09 09 09 = (L+R)/2;.....
0260: 28 63 61 6e 50 6c 61 63 65 28 43 2c 20 78 61 2c (canPlace(C, xa,
0270: 20 79 61 2c 20 78 62 2c 20 79 62 29 3f 4c 3a 52 ya, xb, yb)?L:R
0280: 29 20 3d 20 43 3b 0d 0a 09 09 7d 0d 0a 09 09 72 ) = C;....}....r
0290: 65 74 75 72 6e 20 4c 3b 0d 0a 09 7d 0d 0a 0d 0a eturn L;...}....
02a0: 09 74 79 70 65 64 65 66 20 76 65 63 74 6f 72 3c .typedef vector<
02b0: 20 76 65 63 74 6f 72 3c 69 6e 74 3e 20 3e 20 67 vector<int> > g
02c0: 72 61 70 68 3b 0d 0a 0d 0a 09 62 6f 6f 6c 20 63 raph;.....bool c
02d0: 61 6e 50 6c 61 63 65 28 69 6e 74 20 43 2c 20 76 anPlace(int C, v
02e0: 65 63 74 6f 72 20 3c 69 6e 74 3e 20 78 61 2c 20 ector <int> xa,
02f0: 76 65 63 74 6f 72 20 3c 69 6e 74 3e 20 79 61 2c vector <int> ya,
0300: 20 76 65 63 74 6f 72 20 3c 69 6e 74 3e 20 78 62 vector <int> xb
0310: 2c 20 76 65 63 74 6f 72 20 3c 69 6e 74 3e 20 79 , vector <int> y
0320: 62 29 0d 0a 09 7b 0d 0a 09 09 69 6e 74 20 4e 20 b)...{....int N
0330: 3d 20 78 61 2e 73 69 7a 65 28 29 3b 0d 0a 0d 0a = xa.size();....
0340: 09 09 67 72 61 70 68 20 47 28 32 2a 4e 29 3b 0d ..graph G(2*N);.
0350: 0a 09 09 66 6f 72 28 69 6e 74 20 69 3d 30 3b 20 ...for(int i=0;
0360: 69 3c 4e 3b 20 2b 2b 69 29 20 7b 0d 0a 09 09 09 i<N; ++i) {.....
0370: 66 6f 72 28 69 6e 74 20 6a 3d 30 3b 20 6a 3c 4e for(int j=0; j<N
0380: 3b 20 2b 2b 6a 29 20 69 66 28 69 21 3d 6a 29 0d ; ++j) if(i!=j).
0390: 0a 09 09 09 09 69 66 28 20 21 6f 6b 28 43 2c 20 .....if( !ok(C,
03a0: 78 61 5b 69 5d 2c 20 79 61 5b 69 5d 2c 20 78 61 xa[i], ya[i], xa
03b0: 5b 6a 5d 2c 20 79 61 5b 6a 5d 29 20 29 0d 0a 09 [j], ya[j]) )...
03c0: 09 09 09 09 47 5b 69 5d 2e 70 75 73 68 5f 62 61 ....G[i].push_ba
03d0: 63 6b 28 4e 2b 6a 29 3b 0d 0a 09 09 09 66 6f 72 ck(N+j);.....for
03e0: 28 69 6e 74 20 6a 3d 30 3b 20 6a 3c 4e 3b 20 2b (int j=0; j<N; +
03f0: 2b 6a 29 20 69 66 28 69 21 3d 6a 29 0d 0a 09 09 +j) if(i!=j)....
0400: 09 09 69 66 28 20 21 6f 6b 28 43 2c 20 78 61 5b ..if( !ok(C, xa[
0410: 69 5d 2c 20 79 61 5b 69 5d 2c 20 78 62 5b 6a 5d i], ya[i], xb[j]
0420: 2c 20 79 62 5b 6a 5d 29 20 29 0d 0a 09 09 09 09 , yb[j]) )......
0430: 09 47 5b 69 5d 2e 70 75 73 68 5f 62 61 63 6b 28 .G[i].push_back(
0440: 6a 29 3b 0d 0a 09 09 09 66 6f 72 28 69 6e 74 20 j);.....for(int
0450: 6a 3d 30 3b 20 6a 3c 4e 3b 20 2b 2b 6a 29 20 69 j=0; j<N; ++j) i
0460: 66 28 69 21 3d 6a 29 0d 0a 09 09 09 09 69 66 28 f(i!=j)......if(
0470: 20 21 6f 6b 28 43 2c 20 78 62 5b 69 5d 2c 20 79 !ok(C, xb[i], y
0480: 62 5b 69 5d 2c 20 78 61 5b 6a 5d 2c 20 79 61 5b b[i], xa[j], ya[
0490: 6a 5d 29 20 29 0d 0a 09 09 09 09 09 47 5b 4e 2b j]) ).......G[N+
04a0: 69 5d 2e 70 75 73 68 5f 62 61 63 6b 28 4e 2b 6a i].push_back(N+j
04b0: 29 3b 0d 0a 09 09 09 66 6f 72 28 69 6e 74 20 6a );.....for(int j
04c0: 3d 30 3b 20 6a 3c 4e 3b 20 2b 2b 6a 29 20 69 66 =0; j<N; ++j) if
04d0: 28 69 21 3d 6a 29 0d 0a 09 09 09 09 69 66 28 20 (i!=j)......if(
04e0: 21 6f 6b 28 43 2c 20 78 62 5b 69 5d 2c 20 79 62 !ok(C, xb[i], yb
04f0: 5b 69 5d 2c 20 78 62 5b 6a 5d 2c 20 79 62 5b 6a [i], xb[j], yb[j
0500: 5d 29 20 29 0d 0a 09 09 09 09 09 47 5b 4e 2b 69 ]) ).......G[N+i
0510: 5d 2e 70 75 73 68 5f 62 61 63 6b 28 6a 29 3b 0d ].push_back(j);.
0520: 0a 09 09 7d 0d 0a 0d 0a 09 09 66 6f 72 28 69 6e ...}......for(in
0530: 74 20 69 3d 30 3b 20 69 3c 4e 3b 20 2b 2b 69 29 t i=0; i<N; ++i)
0540: 0d 0a 09 09 09 69 66 28 20 72 65 61 63 68 61 62 .....if( reachab
0550: 6c 65 28 47 2c 69 2c 4e 2b 69 29 20 26 26 20 72 le(G,i,N+i) && r
0560: 65 61 63 68 61 62 6c 65 28 47 2c 4e 2b 69 2c 69 eachable(G,N+i,i
0570: 29 20 29 0d 0a 09 09 09 09 72 65 74 75 72 6e 20 ) )......return
0580: 66 61 6c 73 65 3b 0d 0a 09 09 72 65 74 75 72 6e false;....return
0590: 20 74 72 75 65 3b 0d 0a 09 7d 0d 0a 0d 0a 09 62 true;...}.....b
05a0: 6f 6f 6c 20 72 65 61 63 68 61 62 6c 65 28 67 72 ool reachable(gr
05b0: 61 70 68 26 20 47 2c 20 69 6e 74 20 73 2c 20 69 aph& G, int s, i
05c0: 6e 74 20 64 29 0d 0a 09 7b 0d 0a 09 09 73 65 74 nt d)...{....set
05d0: 3c 69 6e 74 3e 20 56 3b 0d 0a 09 09 71 75 65 75 <int> V;....queu
05e0: 65 3c 69 6e 74 3e 20 51 3b 0d 0a 09 09 51 2e 70 e<int> Q;....Q.p
05f0: 75 73 68 28 73 29 3b 0d 0a 09 09 56 2e 69 6e 73 ush(s);....V.ins
0600: 65 72 74 28 73 29 3b 0d 0a 09 09 77 68 69 6c 65 ert(s);....while
0610: 28 20 21 51 2e 65 6d 70 74 79 28 29 20 29 20 7b ( !Q.empty() ) {
0620: 0d 0a 09 09 09 69 6e 74 20 76 20 3d 20 51 2e 66 .....int v = Q.f
0630: 72 6f 6e 74 28 29 3b 20 51 2e 70 6f 70 28 29 3b ront(); Q.pop();
0640: 0d 0a 09 09 09 66 6f 72 28 69 6e 74 20 69 3d 30 .....for(int i=0
0650: 3b 20 69 3c 47 5b 76 5d 2e 73 69 7a 65 28 29 3b ; i<G[v].size();
0660: 20 2b 2b 69 29 20 7b 0d 0a 09 09 09 09 69 6e 74 ++i) {......int
0670: 20 75 20 3d 20 47 5b 76 5d 5b 69 5d 3b 0d 0a 09 u = G[v][i];...
0680: 09 09 09 69 66 28 20 75 20 3d 3d 20 64 20 29 0d ...if( u == d ).
0690: 0a 09 09 09 09 09 72 65 74 75 72 6e 20 74 72 75 ......return tru
06a0: 65 3b 0d 0a 09 09 09 09 69 66 28 20 21 56 2e 63 e;......if( !V.c
06b0: 6f 75 6e 74 28 75 29 20 29 0d 0a 09 09 09 09 09 ount(u) ).......
06c0: 56 2e 69 6e 73 65 72 74 28 75 29 2c 20 51 2e 70 V.insert(u), Q.p
06d0: 75 73 68 28 75 29 3b 0d 0a 09 09 09 7d 0d 0a 09 ush(u);.....}...
06e0: 09 7d 0d 0a 09 09 72 65 74 75 72 6e 20 66 61 6c .}....return fal
06f0: 73 65 3b 0d 0a 09 7d 0d 0a 0d 0a 09 62 6f 6f 6c se;...}.....bool
0700: 20 6f 6b 28 69 6e 74 20 43 2c 20 69 6e 74 20 78 ok(int C, int x
0710: 31 2c 20 69 6e 74 20 79 31 2c 20 69 6e 74 20 78 1, int y1, int x
0720: 32 2c 20 69 6e 74 20 79 32 29 0d 0a 09 7b 0d 0a 2, int y2)...{..
0730: 09 09 72 65 74 75 72 6e 20 43 20 3c 3d 20 6d 61 ..return C <= ma
0740: 78 28 61 62 73 28 78 31 2d 78 32 29 2c 20 61 62 x(abs(x1-x2), ab
0750: 73 28 79 31 2d 79 32 29 29 3b 0d 0a 09 7d 0d 0a s(y1-y2));...}..
0760: 7d 3b 0d 0a 0d 0a 2f 2f 20 42 45 47 49 4e 20 43 };....// BEGIN C
0770: 55 54 20 48 45 52 45 0d 0a 23 69 6e 63 6c 75 64 UT HERE..#includ
0780: 65 20 3c 63 74 69 6d 65 3e 0d 0a 64 6f 75 62 6c e <ctime>..doubl
0790: 65 20 73 74 61 72 74 5f 74 69 6d 65 3b 20 73 74 e start_time; st
07a0: 72 69 6e 67 20 74 69 6d 65 72 28 29 0d 0a 20 7b ring timer().. {
07b0: 20 6f 73 74 72 69 6e 67 73 74 72 65 61 6d 20 6f ostringstream o
07c0: 73 3b 20 6f 73 20 3c 3c 20 22 20 28 22 20 3c 3c s; os << " (" <<
07d0: 20 69 6e 74 28 28 63 6c 6f 63 6b 28 29 2d 73 74 int((clock()-st
07e0: 61 72 74 5f 74 69 6d 65 29 2f 43 4c 4f 43 4b 53 art_time)/CLOCKS
07f0: 5f 50 45 52 5f 53 45 43 2a 31 30 30 30 29 20 3c _PER_SEC*1000) <
0800: 3c 20 22 20 6d 73 65 63 29 22 3b 20 72 65 74 75 < " msec)"; retu
0810: 72 6e 20 6f 73 2e 73 74 72 28 29 3b 20 7d 0d 0a rn os.str(); }..
0820: 74 65 6d 70 6c 61 74 65 3c 74 79 70 65 6e 61 6d template<typenam
0830: 65 20 54 3e 20 6f 73 74 72 65 61 6d 26 20 6f 70 e T> ostream& op
0840: 65 72 61 74 6f 72 3c 3c 28 6f 73 74 72 65 61 6d erator<<(ostream
0850: 26 20 6f 73 2c 20 63 6f 6e 73 74 20 76 65 63 74 & os, const vect
0860: 6f 72 3c 54 3e 26 20 76 29 0d 0a 20 7b 20 6f 73 or<T>& v).. { os
0870: 20 3c 3c 20 22 7b 20 22 3b 0d 0a 20 20 20 66 6f << "{ ";.. fo
0880: 72 28 74 79 70 65 6e 61 6d 65 20 76 65 63 74 6f r(typename vecto
0890: 72 3c 54 3e 3a 3a 63 6f 6e 73 74 5f 69 74 65 72 r<T>::const_iter
08a0: 61 74 6f 72 20 69 74 3d 76 2e 62 65 67 69 6e 28 ator it=v.begin(
08b0: 29 3b 20 69 74 21 3d 76 2e 65 6e 64 28 29 3b 20 ); it!=v.end();
08c0: 2b 2b 69 74 29 0d 0a 20 20 20 6f 73 20 3c 3c 20 ++it).. os <<
08d0: 27 5c 22 27 20 3c 3c 20 2a 69 74 20 3c 3c 20 27 '\"' << *it << '
08e0: 5c 22 27 20 3c 3c 20 28 69 74 2b 31 3d 3d 76 2e \"' << (it+1==v.
08f0: 65 6e 64 28 29 20 3f 20 22 22 20 3a 20 22 2c 20 end() ? "" : ",
0900: 22 29 3b 20 6f 73 20 3c 3c 20 22 20 7d 22 3b 20 "); os << " }";
0910: 72 65 74 75 72 6e 20 6f 73 3b 20 7d 0d 0a 76 6f return os; }..vo
0920: 69 64 20 76 65 72 69 66 79 5f 63 61 73 65 28 63 id verify_case(c
0930: 6f 6e 73 74 20 69 6e 74 26 20 45 78 70 65 63 74 onst int& Expect
0940: 65 64 2c 20 63 6f 6e 73 74 20 69 6e 74 26 20 52 ed, const int& R
0950: 65 63 65 69 76 65 64 29 20 7b 0d 0a 20 62 6f 6f eceived) {.. boo
0960: 6c 20 6f 6b 20 3d 20 28 45 78 70 65 63 74 65 64 l ok = (Expected
0970: 20 3d 3d 20 52 65 63 65 69 76 65 64 29 3b 0d 0a == Received);..
0980: 20 69 66 28 6f 6b 29 20 63 65 72 72 20 3c 3c 20 if(ok) cerr <<
0990: 22 50 41 53 53 45 44 22 20 3c 3c 20 74 69 6d 65 "PASSED" << time
09a0: 72 28 29 20 3c 3c 20 65 6e 64 6c 3b 20 20 65 6c r() << endl; el
09b0: 73 65 20 7b 20 63 65 72 72 20 3c 3c 20 22 46 41 se { cerr << "FA
09c0: 49 4c 45 44 22 20 3c 3c 20 74 69 6d 65 72 28 29 ILED" << timer()
09d0: 20 3c 3c 20 65 6e 64 6c 3b 0d 0a 20 63 65 72 72 << endl;.. cerr
09e0: 20 3c 3c 20 22 5c 74 6f 3a 20 5c 22 22 20 3c 3c << "\to: \"" <<
09f0: 20 45 78 70 65 63 74 65 64 20 3c 3c 20 27 5c 22 Expected << '\"
0a00: 27 20 3c 3c 20 65 6e 64 6c 20 3c 3c 20 22 5c 74 ' << endl << "\t
0a10: 78 3a 20 5c 22 22 20 3c 3c 20 52 65 63 65 69 76 x: \"" << Receiv
0a20: 65 64 20 3c 3c 20 27 5c 22 27 20 3c 3c 20 65 6e ed << '\"' << en
0a30: 64 6c 3b 20 7d 20 7d 0d 0a 23 64 65 66 69 6e 65 dl; } }..#define
0a40: 20 43 41 53 45 28 4e 29 20 7b 63 65 72 72 20 3c CASE(N) {cerr <
0a50: 3c 20 22 54 65 73 74 20 43 61 73 65 20 23 22 20 < "Test Case #"
0a60: 3c 3c 20 4e 20 3c 3c 20 22 2e 2e 2e 22 20 3c 3c << N << "..." <<
0a70: 20 66 6c 75 73 68 3b 20 73 74 61 72 74 5f 74 69 flush; start_ti
0a80: 6d 65 3d 63 6c 6f 63 6b 28 29 3b 0d 0a 23 64 65 me=clock();..#de
0a90: 66 69 6e 65 20 45 4e 44 09 20 76 65 72 69 66 79 fine END. verify
0aa0: 5f 63 61 73 65 28 5f 2c 20 43 6f 6c 6f 72 66 75 _case(_, Colorfu
0ab0: 6c 44 65 63 6f 72 61 74 69 6f 6e 28 29 2e 67 65 lDecoration().ge
0ac0: 74 4d 61 78 69 6d 75 6d 28 78 61 2c 20 79 61 2c tMaximum(xa, ya,
0ad0: 20 78 62 2c 20 79 62 29 29 3b 7d 0d 0a 69 6e 74 xb, yb));}..int
0ae0: 20 6d 61 69 6e 28 29 7b 0d 0a 0d 0a 43 41 53 45 main(){....CASE
0af0: 28 30 29 0d 0a 09 69 6e 74 20 78 61 5f 5b 5d 20 (0)...int xa_[]
0b00: 3d 20 7b 20 31 30 2c 20 20 30 2c 20 20 37 20 7d = { 10, 0, 7 }
0b10: 3b 0d 0a 09 20 20 76 65 63 74 6f 72 20 3c 69 6e ;... vector <in
0b20: 74 3e 20 78 61 28 78 61 5f 2c 20 78 61 5f 2b 73 t> xa(xa_, xa_+s
0b30: 69 7a 65 6f 66 28 78 61 5f 29 2f 73 69 7a 65 6f izeof(xa_)/sizeo
0b40: 66 28 2a 78 61 5f 29 29 3b 20 0d 0a 09 69 6e 74 f(*xa_)); ...int
0b50: 20 79 61 5f 5b 5d 20 3d 20 7b 20 20 30 2c 20 31 ya_[] = { 0, 1
0b60: 39 2c 20 20 36 20 7d 3b 0d 0a 09 20 20 76 65 63 9, 6 };... vec
0b70: 74 6f 72 20 3c 69 6e 74 3e 20 79 61 28 79 61 5f tor <int> ya(ya_
0b80: 2c 20 79 61 5f 2b 73 69 7a 65 6f 66 28 79 61 5f , ya_+sizeof(ya_
0b90: 29 2f 73 69 7a 65 6f 66 28 2a 79 61 5f 29 29 3b )/sizeof(*ya_));
0ba0: 20 0d 0a 09 69 6e 74 20 78 62 5f 5b 5d 20 3d 20 ...int xb_[] =
0bb0: 7b 20 32 30 2c 20 31 30 2c 20 32 35 20 7d 3b 0d { 20, 10, 25 };.
0bc0: 0a 09 20 20 76 65 63 74 6f 72 20 3c 69 6e 74 3e .. vector <int>
0bd0: 20 78 62 28 78 62 5f 2c 20 78 62 5f 2b 73 69 7a xb(xb_, xb_+siz
0be0: 65 6f 66 28 78 62 5f 29 2f 73 69 7a 65 6f 66 28 eof(xb_)/sizeof(
0bf0: 2a 78 62 5f 29 29 3b 20 0d 0a 09 69 6e 74 20 79 *xb_)); ...int y
0c00: 62 5f 5b 5d 20 3d 20 7b 20 32 30 2c 20 33 35 2c b_[] = { 20, 35,
0c10: 20 32 35 20 7d 3b 0d 0a 09 20 20 76 65 63 74 6f 25 };... vecto
0c20: 72 20 3c 69 6e 74 3e 20 79 62 28 79 62 5f 2c 20 r <int> yb(yb_,
0c30: 79 62 5f 2b 73 69 7a 65 6f 66 28 79 62 5f 29 2f yb_+sizeof(yb_)/
0c40: 73 69 7a 65 6f 66 28 2a 79 62 5f 29 29 3b 20 0d sizeof(*yb_)); .
0c50: 0a 09 69 6e 74 20 5f 20 3d 20 31 39 3b 20 0d 0a ..int _ = 19; ..
0c60: 45 4e 44 0d 0a 43 41 53 45 28 31 29 0d 0a 09 69 END..CASE(1)...i
0c70: 6e 74 20 78 61 5f 5b 5d 20 3d 20 7b 20 34 36 34 nt xa_[] = { 464
0c80: 2c 20 32 30 20 7d 3b 0d 0a 09 20 20 76 65 63 74 , 20 };... vect
0c90: 6f 72 20 3c 69 6e 74 3e 20 78 61 28 78 61 5f 2c or <int> xa(xa_,
0ca0: 20 78 61 5f 2b 73 69 7a 65 6f 66 28 78 61 5f 29 xa_+sizeof(xa_)
0cb0: 2f 73 69 7a 65 6f 66 28 2a 78 61 5f 29 29 3b 20 /sizeof(*xa_));
0cc0: 0d 0a 09 69 6e 74 20 79 61 5f 5b 5d 20 3d 20 7b ...int ya_[] = {
0cd0: 20 34 36 34 2c 20 31 30 20 7d 3b 0d 0a 09 20 20 464, 10 };...
0ce0: 76 65 63 74 6f 72 20 3c 69 6e 74 3e 20 79 61 28 vector <int> ya(
0cf0: 79 61 5f 2c 20 79 61 5f 2b 73 69 7a 65 6f 66 28 ya_, ya_+sizeof(
0d00: 79 61 5f 29 2f 73 69 7a 65 6f 66 28 2a 79 61 5f ya_)/sizeof(*ya_
0d10: 29 29 3b 20 0d 0a 09 69 6e 74 20 78 62 5f 5b 5d )); ...int xb_[]
0d20: 20 3d 20 7b 20 34 36 34 2c 20 20 33 20 7d 3b 0d = { 464, 3 };.
0d30: 0a 09 20 20 76 65 63 74 6f 72 20 3c 69 6e 74 3e .. vector <int>
0d40: 20 78 62 28 78 62 5f 2c 20 78 62 5f 2b 73 69 7a xb(xb_, xb_+siz
0d50: 65 6f 66 28 78 62 5f 29 2f 73 69 7a 65 6f 66 28 eof(xb_)/sizeof(
0d60: 2a 78 62 5f 29 29 3b 20 0d 0a 09 69 6e 74 20 79 *xb_)); ...int y
0d70: 62 5f 5b 5d 20 3d 20 7b 20 34 36 34 2c 20 31 36 b_[] = { 464, 16
0d80: 20 7d 3b 0d 0a 09 20 20 76 65 63 74 6f 72 20 3c };... vector <
0d90: 69 6e 74 3e 20 79 62 28 79 62 5f 2c 20 79 62 5f int> yb(yb_, yb_
0da0: 2b 73 69 7a 65 6f 66 28 79 62 5f 29 2f 73 69 7a +sizeof(yb_)/siz
0db0: 65 6f 66 28 2a 79 62 5f 29 29 3b 20 0d 0a 09 69 eof(*yb_)); ...i
0dc0: 6e 74 20 5f 20 3d 20 34 36 31 3b 20 0d 0a 45 4e nt _ = 461; ..EN
0dd0: 44 0d 0a 43 41 53 45 28 32 29 0d 0a 09 69 6e 74 D..CASE(2)...int
0de0: 20 78 61 5f 5b 5d 20 3d 20 7b 20 30 2c 20 30 2c xa_[] = { 0, 0,
0df0: 20 31 2c 20 31 20 7d 3b 0d 0a 09 20 20 76 65 63 1, 1 };... vec
0e00: 74 6f 72 20 3c 69 6e 74 3e 20 78 61 28 78 61 5f tor <int> xa(xa_
0e10: 2c 20 78 61 5f 2b 73 69 7a 65 6f 66 28 78 61 5f , xa_+sizeof(xa_
0e20: 29 2f 73 69 7a 65 6f 66 28 2a 78 61 5f 29 29 3b )/sizeof(*xa_));
0e30: 20 0d 0a 09 69 6e 74 20 79 61 5f 5b 5d 20 3d 20 ...int ya_[] =
0e40: 7b 20 30 2c 20 30 2c 20 31 2c 20 31 20 7d 3b 0d { 0, 0, 1, 1 };.
0e50: 0a 09 20 20 76 65 63 74 6f 72 20 3c 69 6e 74 3e .. vector <int>
0e60: 20 79 61 28 79 61 5f 2c 20 79 61 5f 2b 73 69 7a ya(ya_, ya_+siz
0e70: 65 6f 66 28 79 61 5f 29 2f 73 69 7a 65 6f 66 28 eof(ya_)/sizeof(
0e80: 2a 79 61 5f 29 29 3b 20 0d 0a 09 69 6e 74 20 78 *ya_)); ...int x
0e90: 62 5f 5b 5d 20 3d 20 7b 20 31 2c 20 31 2c 20 30 b_[] = { 1, 1, 0
0ea0: 2c 20 30 20 7d 3b 0d 0a 09 20 20 76 65 63 74 6f , 0 };... vecto
0eb0: 72 20 3c 69 6e 74 3e 20 78 62 28 78 62 5f 2c 20 r <int> xb(xb_,
0ec0: 78 62 5f 2b 73 69 7a 65 6f 66 28 78 62 5f 29 2f xb_+sizeof(xb_)/
0ed0: 73 69 7a 65 6f 66 28 2a 78 62 5f 29 29 3b 20 0d sizeof(*xb_)); .
0ee0: 0a 09 69 6e 74 20 79 62 5f 5b 5d 20 3d 20 7b 20 ..int yb_[] = {
0ef0: 31 2c 20 31 2c 20 30 2c 20 30 20 7d 3b 0d 0a 09 1, 1, 0, 0 };...
0f00: 20 20 76 65 63 74 6f 72 20 3c 69 6e 74 3e 20 79 vector <int> y
0f10: 62 28 79 62 5f 2c 20 79 62 5f 2b 73 69 7a 65 6f b(yb_, yb_+sizeo
0f20: 66 28 79 62 5f 29 2f 73 69 7a 65 6f 66 28 2a 79 f(yb_)/sizeof(*y
0f30: 62 5f 29 29 3b 20 0d 0a 09 69 6e 74 20 5f 20 3d b_)); ...int _ =
0f40: 20 30 3b 20 0d 0a 45 4e 44 0d 0a 43 41 53 45 28 0; ..END..CASE(
0f50: 33 29 0d 0a 09 69 6e 74 20 78 61 5f 5b 5d 20 3d 3)...int xa_[] =
0f60: 20 7b 20 30 2c 20 33 2c 20 30 2c 20 35 2c 20 36 { 0, 3, 0, 5, 6
0f70: 20 7d 3b 0d 0a 09 20 20 76 65 63 74 6f 72 20 3c };... vector <
0f80: 69 6e 74 3e 20 78 61 28 78 61 5f 2c 20 78 61 5f int> xa(xa_, xa_
0f90: 2b 73 69 7a 65 6f 66 28 78 61 5f 29 2f 73 69 7a +sizeof(xa_)/siz
0fa0: 65 6f 66 28 2a 78 61 5f 29 29 3b 20 0d 0a 09 69 eof(*xa_)); ...i
0fb0: 6e 74 20 79 61 5f 5b 5d 20 3d 20 7b 20 31 2c 20 nt ya_[] = { 1,
0fc0: 36 2c 20 30 2c 20 38 2c 20 35 20 7d 3b 0d 0a 09 6, 0, 8, 5 };...
0fd0: 20 20 76 65 63 74 6f 72 20 3c 69 6e 74 3e 20 79 vector <int> y
0fe0: 61 28 79 61 5f 2c 20 79 61 5f 2b 73 69 7a 65 6f a(ya_, ya_+sizeo
0ff0: 66 28 79 61 5f 29 2f 73 69 7a 65 6f 66 28 2a 79 f(ya_)/sizeof(*y
1000: 61 5f 29 29 3b 20 0d 0a 09 69 6e 74 20 78 62 5f a_)); ...int xb_
1010: 5b 5d 20 3d 20 7b 20 36 2c 20 31 2c 20 37 2c 20 [] = { 6, 1, 7,
1020: 34 2c 20 37 20 7d 3b 0d 0a 09 20 20 76 65 63 74 4, 7 };... vect
1030: 6f 72 20 3c 69 6e 74 3e 20 78 62 28 78 62 5f 2c or <int> xb(xb_,
1040: 20 78 62 5f 2b 73 69 7a 65 6f 66 28 78 62 5f 29 xb_+sizeof(xb_)
1050: 2f 73 69 7a 65 6f 66 28 2a 78 62 5f 29 29 3b 20 /sizeof(*xb_));
1060: 0d 0a 09 69 6e 74 20 79 62 5f 5b 5d 20 3d 20 7b ...int yb_[] = {
1070: 20 35 2c 20 39 2c 20 32 2c 20 38 2c 20 39 20 7d 5, 9, 2, 8, 9 }
1080: 3b 0d 0a 09 20 20 76 65 63 74 6f 72 20 3c 69 6e ;... vector <in
1090: 74 3e 20 79 62 28 79 62 5f 2c 20 79 62 5f 2b 73 t> yb(yb_, yb_+s
10a0: 69 7a 65 6f 66 28 79 62 5f 29 2f 73 69 7a 65 6f izeof(yb_)/sizeo
10b0: 66 28 2a 79 62 5f 29 29 3b 20 0d 0a 09 69 6e 74 f(*yb_)); ...int
10c0: 20 5f 20 3d 20 33 3b 20 0d 0a 45 4e 44 0d 0a 43 _ = 3; ..END..C
10d0: 41 53 45 28 34 29 0d 0a 09 69 6e 74 20 78 61 5f ASE(4)...int xa_
10e0: 5b 5d 20 3d 20 7b 20 31 30 30 30 30 30 30 30 30 [] = { 100000000
10f0: 30 2c 20 30 20 7d 3b 0d 0a 09 20 20 76 65 63 74 0, 0 };... vect
1100: 6f 72 20 3c 69 6e 74 3e 20 78 61 28 78 61 5f 2c or <int> xa(xa_,
1110: 20 78 61 5f 2b 73 69 7a 65 6f 66 28 78 61 5f 29 xa_+sizeof(xa_)
1120: 2f 73 69 7a 65 6f 66 28 2a 78 61 5f 29 29 3b 20 /sizeof(*xa_));
1130: 0d 0a 09 69 6e 74 20 79 61 5f 5b 5d 20 3d 20 7b ...int ya_[] = {
1140: 20 30 2c 20 31 30 30 30 30 30 30 30 30 30 20 7d 0, 1000000000 }
1150: 3b 0d 0a 09 20 20 76 65 63 74 6f 72 20 3c 69 6e ;... vector <in
1160: 74 3e 20 79 61 28 79 61 5f 2c 20 79 61 5f 2b 73 t> ya(ya_, ya_+s
1170: 69 7a 65 6f 66 28 79 61 5f 29 2f 73 69 7a 65 6f izeof(ya_)/sizeo
1180: 66 28 2a 79 61 5f 29 29 3b 20 0d 0a 09 69 6e 74 f(*ya_)); ...int
1190: 20 78 62 5f 5b 5d 20 3d 20 7b 20 30 2c 20 31 30 xb_[] = { 0, 10
11a0: 30 30 30 30 30 30 30 30 20 7d 3b 0d 0a 09 20 20 00000000 };...
11b0: 76 65 63 74 6f 72 20 3c 69 6e 74 3e 20 78 62 28 vector <int> xb(
11c0: 78 62 5f 2c 20 78 62 5f 2b 73 69 7a 65 6f 66 28 xb_, xb_+sizeof(
11d0: 78 62 5f 29 2f 73 69 7a 65 6f 66 28 2a 78 62 5f xb_)/sizeof(*xb_
11e0: 29 29 3b 20 0d 0a 09 69 6e 74 20 79 62 5f 5b 5d )); ...int yb_[]
11f0: 20 3d 20 7b 20 30 2c 20 31 30 30 30 30 30 30 30 = { 0, 10000000
1200: 30 30 20 7d 3b 0d 0a 09 20 20 76 65 63 74 6f 72 00 };... vector
1210: 20 3c 69 6e 74 3e 20 79 62 28 79 62 5f 2c 20 79 <int> yb(yb_, y
1220: 62 5f 2b 73 69 7a 65 6f 66 28 79 62 5f 29 2f 73 b_+sizeof(yb_)/s
1230: 69 7a 65 6f 66 28 2a 79 62 5f 29 29 3b 20 0d 0a izeof(*yb_)); ..
1240: 09 69 6e 74 20 5f 20 3d 20 31 30 30 30 30 30 30 .int _ = 1000000
1250: 30 30 30 3b 20 0d 0a 45 4e 44 0d 0a 43 41 53 45 000; ..END..CASE
1260: 28 35 29 0d 0a 09 69 6e 74 20 78 61 5f 5b 5d 20 (5)...int xa_[]
1270: 3d 20 7b 30 2c 30 7d 3b 0d 0a 09 20 20 76 65 63 = {0,0};... vec
1280: 74 6f 72 20 3c 69 6e 74 3e 20 78 61 28 78 61 5f tor <int> xa(xa_
1290: 2c 20 78 61 5f 2b 73 69 7a 65 6f 66 28 78 61 5f , xa_+sizeof(xa_
12a0: 29 2f 73 69 7a 65 6f 66 28 2a 78 61 5f 29 29 3b )/sizeof(*xa_));
12b0: 20 0d 0a 09 69 6e 74 20 79 61 5f 5b 5d 20 3d 20 ...int ya_[] =
12c0: 7b 30 2c 30 7d 3b 0d 0a 09 20 20 76 65 63 74 6f {0,0};... vecto
12d0: 72 20 3c 69 6e 74 3e 20 79 61 28 79 61 5f 2c 20 r <int> ya(ya_,
12e0: 79 61 5f 2b 73 69 7a 65 6f 66 28 79 61 5f 29 2f ya_+sizeof(ya_)/
12f0: 73 69 7a 65 6f 66 28 2a 79 61 5f 29 29 3b 20 0d sizeof(*ya_)); .
1300: 0a 09 69 6e 74 20 78 62 5f 5b 5d 20 3d 20 7b 30 ..int xb_[] = {0
1310: 2c 30 7d 3b 0d 0a 09 20 20 76 65 63 74 6f 72 20 ,0};... vector
1320: 3c 69 6e 74 3e 20 78 62 28 78 62 5f 2c 20 78 62 <int> xb(xb_, xb
1330: 5f 2b 73 69 7a 65 6f 66 28 78 62 5f 29 2f 73 69 _+sizeof(xb_)/si
1340: 7a 65 6f 66 28 2a 78 62 5f 29 29 3b 20 0d 0a 09 zeof(*xb_)); ...
1350: 69 6e 74 20 79 62 5f 5b 5d 20 3d 20 7b 30 2c 30 int yb_[] = {0,0
1360: 7d 3b 0d 0a 09 20 20 76 65 63 74 6f 72 20 3c 69 };... vector <i
1370: 6e 74 3e 20 79 62 28 79 62 5f 2c 20 79 62 5f 2b nt> yb(yb_, yb_+
1380: 73 69 7a 65 6f 66 28 79 62 5f 29 2f 73 69 7a 65 sizeof(yb_)/size
1390: 6f 66 28 2a 79 62 5f 29 29 3b 20 0d 0a 09 69 6e of(*yb_)); ...in
13a0: 74 20 5f 20 3d 20 30 3b 20 0d 0a 45 4e 44 0d 0a t _ = 0; ..END..
13b0: 43 41 53 45 28 36 29 0d 0a 09 69 6e 74 20 78 61 CASE(6)...int xa
13c0: 5f 5b 5d 20 3d 20 7b 30 2c 30 7d 3b 0d 0a 09 20 _[] = {0,0};...
13d0: 20 76 65 63 74 6f 72 20 3c 69 6e 74 3e 20 78 61 vector <int> xa
13e0: 28 78 61 5f 2c 20 78 61 5f 2b 73 69 7a 65 6f 66 (xa_, xa_+sizeof
13f0: 28 78 61 5f 29 2f 73 69 7a 65 6f 66 28 2a 78 61 (xa_)/sizeof(*xa
1400: 5f 29 29 3b 20 0d 0a 09 69 6e 74 20 79 61 5f 5b _)); ...int ya_[
1410: 5d 20 3d 20 7b 30 2c 30 7d 3b 0d 0a 09 20 20 76 ] = {0,0};... v
1420: 65 63 74 6f 72 20 3c 69 6e 74 3e 20 79 61 28 79 ector <int> ya(y
1430: 61 5f 2c 20 79 61 5f 2b 73 69 7a 65 6f 66 28 79 a_, ya_+sizeof(y
1440: 61 5f 29 2f 73 69 7a 65 6f 66 28 2a 79 61 5f 29 a_)/sizeof(*ya_)
1450: 29 3b 20 0d 0a 09 69 6e 74 20 78 62 5f 5b 5d 20 ); ...int xb_[]
1460: 3d 20 7b 31 2c 31 7d 3b 0d 0a 09 20 20 76 65 63 = {1,1};... vec
1470: 74 6f 72 20 3c 69 6e 74 3e 20 78 62 28 78 62 5f tor <int> xb(xb_
1480: 2c 20 78 62 5f 2b 73 69 7a 65 6f 66 28 78 62 5f , xb_+sizeof(xb_
1490: 29 2f 73 69 7a 65 6f 66 28 2a 78 62 5f 29 29 3b )/sizeof(*xb_));
14a0: 20 0d 0a 09 69 6e 74 20 79 62 5f 5b 5d 20 3d 20 ...int yb_[] =
14b0: 7b 31 2c 31 7d 3b 0d 0a 09 20 20 76 65 63 74 6f {1,1};... vecto
14c0: 72 20 3c 69 6e 74 3e 20 79 62 28 79 62 5f 2c 20 r <int> yb(yb_,
14d0: 79 62 5f 2b 73 69 7a 65 6f 66 28 79 62 5f 29 2f yb_+sizeof(yb_)/
14e0: 73 69 7a 65 6f 66 28 2a 79 62 5f 29 29 3b 20 0d sizeof(*yb_)); .
14f0: 0a 09 69 6e 74 20 5f 20 3d 20 31 3b 20 0d 0a 45 ..int _ = 1; ..E
1500: 4e 44 0d 0a 43 41 53 45 28 37 29 0d 0a 09 69 6e ND..CASE(7)...in
1510: 74 20 78 61 5f 5b 5d 20 3d 20 7b 30 2c 31 2c 32 t xa_[] = {0,1,2
1520: 2c 33 2c 34 2c 35 2c 36 2c 37 2c 38 2c 39 2c 30 ,3,4,5,6,7,8,9,0
1530: 2c 31 2c 32 2c 33 2c 34 2c 35 2c 36 2c 37 2c 38 ,1,2,3,4,5,6,7,8
1540: 2c 39 2c 30 2c 31 2c 32 2c 33 2c 34 2c 35 2c 36 ,9,0,1,2,3,4,5,6
1550: 2c 37 2c 38 2c 39 2c 30 2c 31 2c 32 2c 33 2c 34 ,7,8,9,0,1,2,3,4
1560: 2c 35 2c 36 2c 37 2c 38 2c 39 2c 30 2c 31 2c 32 ,5,6,7,8,9,0,1,2
1570: 2c 33 2c 34 2c 35 2c 36 2c 37 2c 38 2c 39 7d 3b ,3,4,5,6,7,8,9};
1580: 0d 0a 09 20 20 76 65 63 74 6f 72 20 3c 69 6e 74 ... vector <int
1590: 3e 20 78 61 28 78 61 5f 2c 20 78 61 5f 2b 73 69 > xa(xa_, xa_+si
15a0: 7a 65 6f 66 28 78 61 5f 29 2f 73 69 7a 65 6f 66 zeof(xa_)/sizeof
15b0: 28 2a 78 61 5f 29 29 3b 20 0d 0a 09 69 6e 74 20 (*xa_)); ...int
15c0: 79 61 5f 5b 5d 20 3d 20 7b 31 2c 32 2c 33 2c 34 ya_[] = {1,2,3,4
15d0: 2c 35 2c 36 2c 37 2c 38 2c 39 2c 30 2c 31 2c 32 ,5,6,7,8,9,0,1,2
15e0: 2c 33 2c 34 2c 35 2c 36 2c 37 2c 38 2c 39 2c 30 ,3,4,5,6,7,8,9,0
15f0: 2c 31 2c 32 2c 33 2c 34 2c 35 2c 36 2c 37 2c 38 ,1,2,3,4,5,6,7,8
1600: 2c 39 2c 30 2c 31 2c 32 2c 33 2c 34 2c 35 2c 36 ,9,0,1,2,3,4,5,6
1610: 2c 37 2c 38 2c 39 2c 30 2c 31 2c 32 2c 33 2c 34 ,7,8,9,0,1,2,3,4
1620: 2c 35 2c 36 2c 37 2c 38 2c 39 2c 31 30 7d 3b 0d ,5,6,7,8,9,10};.
1630: 0a 09 20 20 76 65 63 74 6f 72 20 3c 69 6e 74 3e .. vector <int>
1640: 20 79 61 28 79 61 5f 2c 20 79 61 5f 2b 73 69 7a ya(ya_, ya_+siz
1650: 65 6f 66 28 79 61 5f 29 2f 73 69 7a 65 6f 66 28 eof(ya_)/sizeof(
1660: 2a 79 61 5f 29 29 3b 20 0d 0a 09 69 6e 74 20 78 *ya_)); ...int x
1670: 62 5f 5b 5d 20 3d 20 7b 32 2c 33 2c 34 2c 35 2c b_[] = {2,3,4,5,
1680: 36 2c 37 2c 38 2c 39 2c 30 2c 31 2c 32 2c 33 2c 6,7,8,9,0,1,2,3,
1690: 34 2c 35 2c 36 2c 37 2c 38 2c 39 2c 30 2c 31 2c 4,5,6,7,8,9,0,1,
16a0: 32 2c 33 2c 34 2c 35 2c 36 2c 37 2c 38 2c 39 2c 2,3,4,5,6,7,8,9,
16b0: 30 2c 31 2c 32 2c 33 2c 34 2c 35 2c 36 2c 37 2c 0,1,2,3,4,5,6,7,
16c0: 38 2c 39 2c 30 2c 31 2c 32 2c 33 2c 34 2c 35 2c 8,9,0,1,2,3,4,5,
16d0: 36 2c 37 2c 38 2c 39 2c 31 30 2c 31 31 7d 3b 0d 6,7,8,9,10,11};.
16e0: 0a 09 20 20 76 65 63 74 6f 72 20 3c 69 6e 74 3e .. vector <int>
16f0: 20 78 62 28 78 62 5f 2c 20 78 62 5f 2b 73 69 7a xb(xb_, xb_+siz
1700: 65 6f 66 28 78 62 5f 29 2f 73 69 7a 65 6f 66 28 eof(xb_)/sizeof(
1710: 2a 78 62 5f 29 29 3b 20 0d 0a 09 69 6e 74 20 79 *xb_)); ...int y
1720: 62 5f 5b 5d 20 3d 20 7b 33 2c 34 2c 35 2c 36 2c b_[] = {3,4,5,6,
1730: 37 2c 38 2c 39 2c 30 2c 31 2c 32 2c 33 2c 34 2c 7,8,9,0,1,2,3,4,
1740: 35 2c 36 2c 37 2c 38 2c 39 2c 30 2c 31 2c 32 2c 5,6,7,8,9,0,1,2,
1750: 33 2c 34 2c 35 2c 36 2c 37 2c 38 2c 39 2c 30 2c 3,4,5,6,7,8,9,0,
1760: 31 2c 32 2c 33 2c 34 2c 35 2c 36 2c 37 2c 38 2c 1,2,3,4,5,6,7,8,
1770: 39 2c 30 2c 31 2c 32 2c 33 2c 34 2c 35 2c 36 2c 9,0,1,2,3,4,5,6,
1780: 37 2c 38 2c 39 2c 31 30 2c 31 31 2c 31 32 7d 3b 7,8,9,10,11,12};
1790: 0d 0a 09 20 20 76 65 63 74 6f 72 20 3c 69 6e 74 ... vector <int
17a0: 3e 20 79 62 28 79 62 5f 2c 20 79 62 5f 2b 73 69 > yb(yb_, yb_+si
17b0: 7a 65 6f 66 28 79 62 5f 29 2f 73 69 7a 65 6f 66 zeof(yb_)/sizeof
17c0: 28 2a 79 62 5f 29 29 3b 20 0d 0a 09 69 6e 74 20 (*yb_)); ...int
17d0: 5f 20 3d 20 2d 31 3b 20 0d 0a 45 4e 44 0d 0a 0d _ = -1; ..END...
17e0: 0a 7d 0d 0a 2f 2f 20 45 4e 44 20 43 55 54 20 48 .}..// END CUT H
17f0: 45 52 45 0d 0a ERE..