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 63 6f 6d 70 L;..typedef comp
0170: 6c 65 78 3c 64 6f 75 62 6c 65 3e 20 43 4d 50 3b lex<double> CMP;
0180: 0d 0a 0d 0a 63 6c 61 73 73 20 43 61 6e 64 79 4f ....class CandyO
0190: 6e 44 69 73 6b 20 7b 20 70 75 62 6c 69 63 3a 0d nDisk { public:.
01a0: 0a 09 73 74 72 69 6e 67 20 61 62 6c 65 54 6f 41 ..string ableToA
01b0: 63 68 69 65 76 65 28 76 65 63 74 6f 72 20 3c 69 chieve(vector <i
01c0: 6e 74 3e 20 78 5f 2c 20 76 65 63 74 6f 72 20 3c nt> x_, vector <
01d0: 69 6e 74 3e 20 79 5f 2c 20 76 65 63 74 6f 72 20 int> y_, vector
01e0: 3c 69 6e 74 3e 20 72 5f 2c 20 69 6e 74 20 73 78 <int> r_, int sx
01f0: 2c 20 69 6e 74 20 73 79 2c 20 69 6e 74 20 74 78 , int sy, int tx
0200: 2c 20 69 6e 74 20 74 79 29 0d 0a 09 7b 0d 0a 09 , int ty)...{...
0210: 09 69 66 28 73 78 3d 3d 74 78 20 26 26 20 73 79 .if(sx==tx && sy
0220: 3d 3d 74 79 29 0d 0a 09 09 09 72 65 74 75 72 6e ==ty).....return
0230: 20 22 59 45 53 22 3b 0d 0a 0d 0a 09 09 76 65 63 "YES";......vec
0240: 74 6f 72 3c 4c 4c 3e 20 78 2c 79 2c 72 3b 0d 0a tor<LL> x,y,r;..
0250: 09 09 7b 0d 0a 09 09 09 6d 61 70 3c 70 61 69 72 ..{.....map<pair
0260: 3c 4c 4c 2c 4c 4c 3e 2c 4c 4c 3e 20 78 79 72 3b <LL,LL>,LL> xyr;
0270: 0d 0a 09 09 09 66 6f 72 28 69 6e 74 20 69 3d 30 .....for(int i=0
0280: 3b 20 69 3c 78 5f 2e 73 69 7a 65 28 29 3b 20 2b ; i<x_.size(); +
0290: 2b 69 29 0d 0a 09 09 09 09 78 79 72 5b 6d 61 6b +i)......xyr[mak
02a0: 65 5f 70 61 69 72 28 78 5f 5b 69 5d 2c 79 5f 5b e_pair(x_[i],y_[
02b0: 69 5d 29 5d 20 3d 20 6d 61 78 3c 4c 4c 3e 28 78 i])] = max<LL>(x
02c0: 79 72 5b 6d 61 6b 65 5f 70 61 69 72 28 78 5f 5b yr[make_pair(x_[
02d0: 69 5d 2c 79 5f 5b 69 5d 29 5d 2c 20 72 5f 5b 69 i],y_[i])], r_[i
02e0: 5d 29 3b 0d 0a 09 09 09 66 6f 72 28 6d 61 70 3c ]);.....for(map<
02f0: 70 61 69 72 3c 4c 4c 2c 4c 4c 3e 2c 4c 4c 3e 3a pair<LL,LL>,LL>:
0300: 3a 69 74 65 72 61 74 6f 72 20 69 74 3d 78 79 72 :iterator it=xyr
0310: 2e 62 65 67 69 6e 28 29 3b 20 69 74 21 3d 78 79 .begin(); it!=xy
0320: 72 2e 65 6e 64 28 29 3b 20 2b 2b 69 74 29 20 7b r.end(); ++it) {
0330: 0d 0a 09 09 09 09 78 2e 70 75 73 68 5f 62 61 63 ......x.push_bac
0340: 6b 28 69 74 2d 3e 66 69 72 73 74 2e 66 69 72 73 k(it->first.firs
0350: 74 29 3b 0d 0a 09 09 09 09 79 2e 70 75 73 68 5f t);......y.push_
0360: 62 61 63 6b 28 69 74 2d 3e 66 69 72 73 74 2e 73 back(it->first.s
0370: 65 63 6f 6e 64 29 3b 0d 0a 09 09 09 09 72 2e 70 econd);......r.p
0380: 75 73 68 5f 62 61 63 6b 28 69 74 2d 3e 73 65 63 ush_back(it->sec
0390: 6f 6e 64 29 3b 0d 0a 09 09 09 7d 0d 0a 09 09 7d ond);.....}....}
03a0: 0d 0a 0d 0a 09 09 63 6f 6e 73 74 20 69 6e 74 20 ......const int
03b0: 4e 20 3d 20 78 2e 73 69 7a 65 28 29 3b 0d 0a 09 N = x.size();...
03c0: 09 6d 61 70 3c 69 6e 74 2c 20 64 6f 75 62 6c 65 .map<int, double
03d0: 3e 20 70 3b 0d 0a 09 09 7b 0d 0a 09 09 09 66 6f > p;....{.....fo
03e0: 72 28 69 6e 74 20 69 3d 30 3b 20 69 3c 4e 3b 20 r(int i=0; i<N;
03f0: 2b 2b 69 29 0d 0a 09 09 09 7b 0d 0a 09 09 09 09 ++i).....{......
0400: 4c 4c 20 64 64 20 3d 20 28 73 78 2d 78 5b 69 5d LL dd = (sx-x[i]
0410: 29 2a 28 73 78 2d 78 5b 69 5d 29 2b 28 73 79 2d )*(sx-x[i])+(sy-
0420: 79 5b 69 5d 29 2a 28 73 79 2d 79 5b 69 5d 29 3b y[i])*(sy-y[i]);
0430: 0d 0a 09 09 09 09 69 66 28 20 64 64 20 3c 3d 20 ......if( dd <=
0440: 72 5b 69 5d 2a 72 5b 69 5d 20 29 0d 0a 09 09 09 r[i]*r[i] ).....
0450: 09 7b 0d 0a 09 09 09 09 09 69 66 28 20 64 64 20 .{.......if( dd
0460: 3d 3d 20 28 74 78 2d 78 5b 69 5d 29 2a 28 74 78 == (tx-x[i])*(tx
0470: 2d 78 5b 69 5d 29 2b 28 74 79 2d 79 5b 69 5d 29 -x[i])+(ty-y[i])
0480: 2a 28 74 79 2d 79 5b 69 5d 29 20 29 0d 0a 09 09 *(ty-y[i]) )....
0490: 09 09 09 09 72 65 74 75 72 6e 20 22 59 45 53 22 ....return "YES"
04a0: 3b 0d 0a 09 09 09 09 09 62 6f 6f 6c 20 6f 6b 20 ;.......bool ok
04b0: 3d 20 66 61 6c 73 65 3b 0d 0a 09 09 09 09 09 66 = false;.......f
04c0: 6f 72 28 69 6e 74 20 6b 3d 30 3b 20 6b 3c 4e 3b or(int k=0; k<N;
04d0: 20 2b 2b 6b 29 20 69 66 28 6b 21 3d 69 29 0d 0a ++k) if(k!=i)..
04e0: 09 09 09 09 09 7b 0d 0a 09 09 09 09 09 09 4c 4c .....{........LL
04f0: 20 64 20 3d 20 28 78 5b 69 5d 2d 78 5b 6b 5d 29 d = (x[i]-x[k])
0500: 2a 28 78 5b 69 5d 2d 78 5b 6b 5d 29 20 2b 20 28 *(x[i]-x[k]) + (
0510: 79 5b 69 5d 2d 79 5b 6b 5d 29 2a 28 79 5b 69 5d y[i]-y[k])*(y[i]
0520: 2d 79 5b 6b 5d 29 3b 0d 0a 09 09 09 09 09 09 69 -y[k]);........i
0530: 66 28 20 64 20 3c 3d 20 28 72 5b 69 5d 2b 72 5b f( d <= (r[i]+r[
0540: 6b 5d 29 2a 28 72 5b 69 5d 2b 72 5b 6b 5d 29 20 k])*(r[i]+r[k])
0550: 29 0d 0a 09 09 09 09 09 09 09 6f 6b 20 3d 20 74 ).........ok = t
0560: 72 75 65 3b 0d 0a 09 09 09 09 09 7d 0d 0a 09 09 rue;.......}....
0570: 09 09 09 69 66 28 6f 6b 29 0d 0a 09 09 09 09 09 ...if(ok).......
0580: 09 70 5b 69 5d 20 3d 20 73 71 72 74 28 28 64 6f .p[i] = sqrt((do
0590: 75 62 6c 65 29 64 64 29 3b 0d 0a 09 09 09 09 7d uble)dd);......}
05a0: 0d 0a 09 09 09 7d 0d 0a 09 09 7d 0d 0a 0d 0a 09 .....}....}.....
05b0: 09 66 6f 72 28 3b 3b 29 0d 0a 09 09 7b 0d 0a 09 .for(;;)....{...
05c0: 09 09 62 6f 6f 6c 20 75 70 64 20 3d 20 66 61 6c ..bool upd = fal
05d0: 73 65 3b 0d 0a 09 09 09 6d 61 70 3c 69 6e 74 2c se;.....map<int,
05e0: 64 6f 75 62 6c 65 3e 20 70 32 20 3d 20 70 3b 0d double> p2 = p;.
05f0: 0a 09 09 09 66 6f 72 28 6d 61 70 3c 69 6e 74 2c ....for(map<int,
0600: 64 6f 75 62 6c 65 3e 3a 3a 69 74 65 72 61 74 6f double>::iterato
0610: 72 20 69 74 3d 70 2e 62 65 67 69 6e 28 29 3b 20 r it=p.begin();
0620: 69 74 21 3d 70 2e 65 6e 64 28 29 3b 20 2b 2b 69 it!=p.end(); ++i
0630: 74 29 0d 0a 09 09 09 7b 0d 0a 09 09 09 09 69 6e t).....{......in
0640: 74 20 69 20 3d 20 69 74 2d 3e 66 69 72 73 74 3b t i = it->first;
0650: 0d 0a 09 09 09 09 64 6f 75 62 6c 65 20 64 20 3d ......double d =
0660: 20 69 74 2d 3e 73 65 63 6f 6e 64 3b 0d 0a 0d 0a it->second;....
0670: 09 09 09 09 4c 4c 20 64 64 20 3d 20 28 74 78 2d ....LL dd = (tx-
0680: 78 5b 69 5d 29 2a 28 74 78 2d 78 5b 69 5d 29 2b x[i])*(tx-x[i])+
0690: 28 74 79 2d 79 5b 69 5d 29 2a 28 74 79 2d 79 5b (ty-y[i])*(ty-y[
06a0: 69 5d 29 3b 0d 0a 09 09 09 09 69 66 28 64 2a 64 i]);......if(d*d
06b0: 20 3c 3d 20 64 64 20 26 26 20 64 64 20 3c 3d 20 <= dd && dd <=
06c0: 72 5b 69 5d 2a 72 5b 69 5d 29 0d 0a 09 09 09 09 r[i]*r[i])......
06d0: 09 72 65 74 75 72 6e 20 22 59 45 53 22 3b 0d 0a .return "YES";..
06e0: 0d 0a 09 09 09 09 66 6f 72 28 69 6e 74 20 6b 3d ......for(int k=
06f0: 30 3b 20 6b 3c 4e 3b 20 2b 2b 6b 29 20 69 66 28 0; k<N; ++k) if(
0700: 6b 21 3d 69 29 0d 0a 09 09 09 09 7b 0d 0a 09 09 k!=i)......{....
0710: 09 09 09 64 6f 75 62 6c 65 20 7a 20 3d 20 61 62 ...double z = ab
0720: 73 28 43 4d 50 28 78 5b 69 5d 2c 79 5b 69 5d 29 s(CMP(x[i],y[i])
0730: 2d 43 4d 50 28 78 5b 6b 5d 2c 79 5b 6b 5d 29 29 -CMP(x[k],y[k]))
0740: 3b 0d 0a 09 09 09 09 09 69 66 28 6d 61 78 28 30 ;.......if(max(0
0750: 2e 30 2c 20 7a 2d 72 5b 6b 5d 29 20 3c 3d 20 64 .0, z-r[k]) <= d
0760: 29 20 7b 0d 0a 09 09 09 09 09 09 64 6f 75 62 6c ) {........doubl
0770: 65 20 64 6b 20 3d 20 6d 61 78 28 30 2e 30 2c 20 e dk = max(0.0,
0780: 7a 2d 72 5b 69 5d 29 3b 0d 0a 09 09 09 09 09 09 z-r[i]);........
0790: 69 66 28 21 70 32 2e 63 6f 75 6e 74 28 6b 29 20 if(!p2.count(k)
07a0: 7c 7c 20 70 32 5b 6b 5d 3e 64 6b 29 20 7b 0d 0a || p2[k]>dk) {..
07b0: 09 09 09 09 09 09 09 75 70 64 20 3d 20 74 72 75 .......upd = tru
07c0: 65 3b 0d 0a 09 09 09 09 09 09 09 70 32 5b 6b 5d e;.........p2[k]
07d0: 20 3d 20 64 6b 3b 0d 0a 09 09 09 09 09 09 7d 0d = dk;........}.
07e0: 0a 09 09 09 09 09 7d 0d 0a 09 09 09 09 7d 0d 0a ......}......}..
07f0: 09 09 09 7d 0d 0a 09 09 09 69 66 28 21 75 70 64 ...}.....if(!upd
0800: 29 0d 0a 09 09 09 09 62 72 65 61 6b 3b 0d 0a 09 )......break;...
0810: 09 09 70 2e 73 77 61 70 28 70 32 29 3b 0d 0a 09 ..p.swap(p2);...
0820: 09 7d 0d 0a 0d 0a 09 09 72 65 74 75 72 6e 20 22 .}......return "
0830: 4e 4f 22 3b 0d 0a 09 7d 0d 0a 7d 3b 0d 0a 0d 0a NO";...}..};....
0840: 2f 2f 20 42 45 47 49 4e 20 43 55 54 20 48 45 52 // BEGIN CUT HER
0850: 45 0d 0a 23 69 6e 63 6c 75 64 65 20 3c 63 74 69 E..#include <cti
0860: 6d 65 3e 0d 0a 64 6f 75 62 6c 65 20 73 74 61 72 me>..double star
0870: 74 5f 74 69 6d 65 3b 20 73 74 72 69 6e 67 20 74 t_time; string t
0880: 69 6d 65 72 28 29 0d 0a 20 7b 20 6f 73 74 72 69 imer().. { ostri
0890: 6e 67 73 74 72 65 61 6d 20 6f 73 3b 20 6f 73 20 ngstream os; os
08a0: 3c 3c 20 22 20 28 22 20 3c 3c 20 69 6e 74 28 28 << " (" << int((
08b0: 63 6c 6f 63 6b 28 29 2d 73 74 61 72 74 5f 74 69 clock()-start_ti
08c0: 6d 65 29 2f 43 4c 4f 43 4b 53 5f 50 45 52 5f 53 me)/CLOCKS_PER_S
08d0: 45 43 2a 31 30 30 30 29 20 3c 3c 20 22 20 6d 73 EC*1000) << " ms
08e0: 65 63 29 22 3b 20 72 65 74 75 72 6e 20 6f 73 2e ec)"; return os.
08f0: 73 74 72 28 29 3b 20 7d 0d 0a 74 65 6d 70 6c 61 str(); }..templa
0900: 74 65 3c 74 79 70 65 6e 61 6d 65 20 54 3e 20 6f te<typename T> o
0910: 73 74 72 65 61 6d 26 20 6f 70 65 72 61 74 6f 72 stream& operator
0920: 3c 3c 28 6f 73 74 72 65 61 6d 26 20 6f 73 2c 20 <<(ostream& os,
0930: 63 6f 6e 73 74 20 76 65 63 74 6f 72 3c 54 3e 26 const vector<T>&
0940: 20 76 29 0d 0a 20 7b 20 6f 73 20 3c 3c 20 22 7b v).. { os << "{
0950: 20 22 3b 0d 0a 20 20 20 66 6f 72 28 74 79 70 65 ";.. for(type
0960: 6e 61 6d 65 20 76 65 63 74 6f 72 3c 54 3e 3a 3a name vector<T>::
0970: 63 6f 6e 73 74 5f 69 74 65 72 61 74 6f 72 20 69 const_iterator i
0980: 74 3d 76 2e 62 65 67 69 6e 28 29 3b 20 69 74 21 t=v.begin(); it!
0990: 3d 76 2e 65 6e 64 28 29 3b 20 2b 2b 69 74 29 0d =v.end(); ++it).
09a0: 0a 20 20 20 6f 73 20 3c 3c 20 27 5c 22 27 20 3c . os << '\"' <
09b0: 3c 20 2a 69 74 20 3c 3c 20 27 5c 22 27 20 3c 3c < *it << '\"' <<
09c0: 20 28 69 74 2b 31 3d 3d 76 2e 65 6e 64 28 29 20 (it+1==v.end()
09d0: 3f 20 22 22 20 3a 20 22 2c 20 22 29 3b 20 6f 73 ? "" : ", "); os
09e0: 20 3c 3c 20 22 20 7d 22 3b 20 72 65 74 75 72 6e << " }"; return
09f0: 20 6f 73 3b 20 7d 0d 0a 76 6f 69 64 20 76 65 72 os; }..void ver
0a00: 69 66 79 5f 63 61 73 65 28 63 6f 6e 73 74 20 73 ify_case(const s
0a10: 74 72 69 6e 67 26 20 45 78 70 65 63 74 65 64 2c tring& Expected,
0a20: 20 63 6f 6e 73 74 20 73 74 72 69 6e 67 26 20 52 const string& R
0a30: 65 63 65 69 76 65 64 29 20 7b 0d 0a 20 62 6f 6f eceived) {.. boo
0a40: 6c 20 6f 6b 20 3d 20 28 45 78 70 65 63 74 65 64 l ok = (Expected
0a50: 20 3d 3d 20 52 65 63 65 69 76 65 64 29 3b 0d 0a == Received);..
0a60: 20 69 66 28 6f 6b 29 20 63 65 72 72 20 3c 3c 20 if(ok) cerr <<
0a70: 22 50 41 53 53 45 44 22 20 3c 3c 20 74 69 6d 65 "PASSED" << time
0a80: 72 28 29 20 3c 3c 20 65 6e 64 6c 3b 20 20 65 6c r() << endl; el
0a90: 73 65 20 7b 20 63 65 72 72 20 3c 3c 20 22 46 41 se { cerr << "FA
0aa0: 49 4c 45 44 22 20 3c 3c 20 74 69 6d 65 72 28 29 ILED" << timer()
0ab0: 20 3c 3c 20 65 6e 64 6c 3b 0d 0a 20 63 65 72 72 << endl;.. cerr
0ac0: 20 3c 3c 20 22 5c 74 6f 3a 20 5c 22 22 20 3c 3c << "\to: \"" <<
0ad0: 20 45 78 70 65 63 74 65 64 20 3c 3c 20 27 5c 22 Expected << '\"
0ae0: 27 20 3c 3c 20 65 6e 64 6c 20 3c 3c 20 22 5c 74 ' << endl << "\t
0af0: 78 3a 20 5c 22 22 20 3c 3c 20 52 65 63 65 69 76 x: \"" << Receiv
0b00: 65 64 20 3c 3c 20 27 5c 22 27 20 3c 3c 20 65 6e ed << '\"' << en
0b10: 64 6c 3b 20 7d 20 7d 0d 0a 23 64 65 66 69 6e 65 dl; } }..#define
0b20: 20 43 41 53 45 28 4e 29 20 7b 63 65 72 72 20 3c CASE(N) {cerr <
0b30: 3c 20 22 54 65 73 74 20 43 61 73 65 20 23 22 20 < "Test Case #"
0b40: 3c 3c 20 4e 20 3c 3c 20 22 2e 2e 2e 22 20 3c 3c << N << "..." <<
0b50: 20 66 6c 75 73 68 3b 20 73 74 61 72 74 5f 74 69 flush; start_ti
0b60: 6d 65 3d 63 6c 6f 63 6b 28 29 3b 0d 0a 23 64 65 me=clock();..#de
0b70: 66 69 6e 65 20 45 4e 44 09 20 76 65 72 69 66 79 fine END. verify
0b80: 5f 63 61 73 65 28 5f 2c 20 43 61 6e 64 79 4f 6e _case(_, CandyOn
0b90: 44 69 73 6b 28 29 2e 61 62 6c 65 54 6f 41 63 68 Disk().ableToAch
0ba0: 69 65 76 65 28 78 2c 20 79 2c 20 72 2c 20 73 78 ieve(x, y, r, sx
0bb0: 2c 20 73 79 2c 20 74 78 2c 20 74 79 29 29 3b 7d , sy, tx, ty));}
0bc0: 0d 0a 69 6e 74 20 6d 61 69 6e 28 29 7b 0d 0a 0d ..int main(){...
0bd0: 0a 43 41 53 45 28 30 29 0d 0a 09 69 6e 74 20 78 .CASE(0)...int x
0be0: 5f 5b 5d 20 3d 20 7b 30 2c 20 34 7d 3b 0d 0a 09 _[] = {0, 4};...
0bf0: 20 20 76 65 63 74 6f 72 20 3c 69 6e 74 3e 20 78 vector <int> x
0c00: 28 78 5f 2c 20 78 5f 2b 73 69 7a 65 6f 66 28 78 (x_, x_+sizeof(x
0c10: 5f 29 2f 73 69 7a 65 6f 66 28 2a 78 5f 29 29 3b _)/sizeof(*x_));
0c20: 20 0d 0a 09 69 6e 74 20 79 5f 5b 5d 20 3d 20 7b ...int y_[] = {
0c30: 30 2c 20 30 7d 3b 0d 0a 09 20 20 76 65 63 74 6f 0, 0};... vecto
0c40: 72 20 3c 69 6e 74 3e 20 79 28 79 5f 2c 20 79 5f r <int> y(y_, y_
0c50: 2b 73 69 7a 65 6f 66 28 79 5f 29 2f 73 69 7a 65 +sizeof(y_)/size
0c60: 6f 66 28 2a 79 5f 29 29 3b 20 0d 0a 09 69 6e 74 of(*y_)); ...int
0c70: 20 72 5f 5b 5d 20 3d 20 7b 33 2c 20 33 7d 3b 0d r_[] = {3, 3};.
0c80: 0a 09 20 20 76 65 63 74 6f 72 20 3c 69 6e 74 3e .. vector <int>
0c90: 20 72 28 72 5f 2c 20 72 5f 2b 73 69 7a 65 6f 66 r(r_, r_+sizeof
0ca0: 28 72 5f 29 2f 73 69 7a 65 6f 66 28 2a 72 5f 29 (r_)/sizeof(*r_)
0cb0: 29 3b 20 0d 0a 09 69 6e 74 20 73 78 20 3d 20 2d ); ...int sx = -
0cc0: 31 3b 20 0d 0a 09 69 6e 74 20 73 79 20 3d 20 2d 1; ...int sy = -
0cd0: 32 3b 20 0d 0a 09 69 6e 74 20 74 78 20 3d 20 36 2; ...int tx = 6
0ce0: 3b 20 0d 0a 09 69 6e 74 20 74 79 20 3d 20 31 3b ; ...int ty = 1;
0cf0: 20 0d 0a 09 73 74 72 69 6e 67 20 5f 20 3d 20 22 ...string _ = "
0d00: 59 45 53 22 3b 20 0d 0a 45 4e 44 0d 0a 43 41 53 YES"; ..END..CAS
0d10: 45 28 31 29 0d 0a 09 69 6e 74 20 78 5f 5b 5d 20 E(1)...int x_[]
0d20: 3d 20 7b 30 2c 20 33 7d 3b 0d 0a 09 20 20 76 65 = {0, 3};... ve
0d30: 63 74 6f 72 20 3c 69 6e 74 3e 20 78 28 78 5f 2c ctor <int> x(x_,
0d40: 20 78 5f 2b 73 69 7a 65 6f 66 28 78 5f 29 2f 73 x_+sizeof(x_)/s
0d50: 69 7a 65 6f 66 28 2a 78 5f 29 29 3b 20 0d 0a 09 izeof(*x_)); ...
0d60: 69 6e 74 20 79 5f 5b 5d 20 3d 20 7b 30 2c 20 30 int y_[] = {0, 0
0d70: 7d 3b 0d 0a 09 20 20 76 65 63 74 6f 72 20 3c 69 };... vector <i
0d80: 6e 74 3e 20 79 28 79 5f 2c 20 79 5f 2b 73 69 7a nt> y(y_, y_+siz
0d90: 65 6f 66 28 79 5f 29 2f 73 69 7a 65 6f 66 28 2a eof(y_)/sizeof(*
0da0: 79 5f 29 29 3b 20 0d 0a 09 69 6e 74 20 72 5f 5b y_)); ...int r_[
0db0: 5d 20 3d 20 7b 35 2c 20 33 7d 3b 0d 0a 09 20 20 ] = {5, 3};...
0dc0: 76 65 63 74 6f 72 20 3c 69 6e 74 3e 20 72 28 72 vector <int> r(r
0dd0: 5f 2c 20 72 5f 2b 73 69 7a 65 6f 66 28 72 5f 29 _, r_+sizeof(r_)
0de0: 2f 73 69 7a 65 6f 66 28 2a 72 5f 29 29 3b 20 0d /sizeof(*r_)); .
0df0: 0a 09 69 6e 74 20 73 78 20 3d 20 2d 34 3b 20 0d ..int sx = -4; .
0e00: 0a 09 69 6e 74 20 73 79 20 3d 20 30 3b 20 0d 0a ..int sy = 0; ..
0e10: 09 69 6e 74 20 74 78 20 3d 20 2d 32 3b 20 0d 0a .int tx = -2; ..
0e20: 09 69 6e 74 20 74 79 20 3d 20 30 3b 20 0d 0a 09 .int ty = 0; ...
0e30: 73 74 72 69 6e 67 20 5f 20 3d 20 22 59 45 53 22 string _ = "YES"
0e40: 3b 20 0d 0a 45 4e 44 0d 0a 43 41 53 45 28 32 29 ; ..END..CASE(2)
0e50: 0d 0a 09 69 6e 74 20 78 5f 5b 5d 20 3d 20 7b 30 ...int x_[] = {0
0e60: 7d 3b 0d 0a 09 20 20 76 65 63 74 6f 72 20 3c 69 };... vector <i
0e70: 6e 74 3e 20 78 28 78 5f 2c 20 78 5f 2b 73 69 7a nt> x(x_, x_+siz
0e80: 65 6f 66 28 78 5f 29 2f 73 69 7a 65 6f 66 28 2a eof(x_)/sizeof(*
0e90: 78 5f 29 29 3b 20 0d 0a 09 69 6e 74 20 79 5f 5b x_)); ...int y_[
0ea0: 5d 20 3d 20 7b 30 7d 3b 0d 0a 09 20 20 76 65 63 ] = {0};... vec
0eb0: 74 6f 72 20 3c 69 6e 74 3e 20 79 28 79 5f 2c 20 tor <int> y(y_,
0ec0: 79 5f 2b 73 69 7a 65 6f 66 28 79 5f 29 2f 73 69 y_+sizeof(y_)/si
0ed0: 7a 65 6f 66 28 2a 79 5f 29 29 3b 20 0d 0a 09 69 zeof(*y_)); ...i
0ee0: 6e 74 20 72 5f 5b 5d 20 3d 20 7b 31 7d 3b 0d 0a nt r_[] = {1};..
0ef0: 09 20 20 76 65 63 74 6f 72 20 3c 69 6e 74 3e 20 . vector <int>
0f00: 72 28 72 5f 2c 20 72 5f 2b 73 69 7a 65 6f 66 28 r(r_, r_+sizeof(
0f10: 72 5f 29 2f 73 69 7a 65 6f 66 28 2a 72 5f 29 29 r_)/sizeof(*r_))
0f20: 3b 20 0d 0a 09 69 6e 74 20 73 78 20 3d 20 30 3b ; ...int sx = 0;
0f30: 20 0d 0a 09 69 6e 74 20 73 79 20 3d 20 30 3b 20 ...int sy = 0;
0f40: 0d 0a 09 69 6e 74 20 74 78 20 3d 20 35 37 31 3b ...int tx = 571;
0f50: 20 0d 0a 09 69 6e 74 20 74 79 20 3d 20 35 37 31 ...int ty = 571
0f60: 3b 20 0d 0a 09 73 74 72 69 6e 67 20 5f 20 3d 20 ; ...string _ =
0f70: 22 4e 4f 22 3b 20 0d 0a 45 4e 44 0d 0a 43 41 53 "NO"; ..END..CAS
0f80: 45 28 33 29 0d 0a 09 69 6e 74 20 78 5f 5b 5d 20 E(3)...int x_[]
0f90: 3d 20 7b 30 7d 3b 0d 0a 09 20 20 76 65 63 74 6f = {0};... vecto
0fa0: 72 20 3c 69 6e 74 3e 20 78 28 78 5f 2c 20 78 5f r <int> x(x_, x_
0fb0: 2b 73 69 7a 65 6f 66 28 78 5f 29 2f 73 69 7a 65 +sizeof(x_)/size
0fc0: 6f 66 28 2a 78 5f 29 29 3b 20 0d 0a 09 69 6e 74 of(*x_)); ...int
0fd0: 20 79 5f 5b 5d 20 3d 20 7b 30 7d 3b 0d 0a 09 20 y_[] = {0};...
0fe0: 20 76 65 63 74 6f 72 20 3c 69 6e 74 3e 20 79 28 vector <int> y(
0ff0: 79 5f 2c 20 79 5f 2b 73 69 7a 65 6f 66 28 79 5f y_, y_+sizeof(y_
1000: 29 2f 73 69 7a 65 6f 66 28 2a 79 5f 29 29 3b 20 )/sizeof(*y_));
1010: 0d 0a 09 69 6e 74 20 72 5f 5b 5d 20 3d 20 7b 31 ...int r_[] = {1
1020: 7d 3b 0d 0a 09 20 20 76 65 63 74 6f 72 20 3c 69 };... vector <i
1030: 6e 74 3e 20 72 28 72 5f 2c 20 72 5f 2b 73 69 7a nt> r(r_, r_+siz
1040: 65 6f 66 28 72 5f 29 2f 73 69 7a 65 6f 66 28 2a eof(r_)/sizeof(*
1050: 72 5f 29 29 3b 20 0d 0a 09 69 6e 74 20 73 78 20 r_)); ...int sx
1060: 3d 20 35 37 31 3b 20 0d 0a 09 69 6e 74 20 73 79 = 571; ...int sy
1070: 20 3d 20 35 37 31 3b 20 0d 0a 09 69 6e 74 20 74 = 571; ...int t
1080: 78 20 3d 20 35 37 31 3b 20 0d 0a 09 69 6e 74 20 x = 571; ...int
1090: 74 79 20 3d 20 35 37 31 3b 20 0d 0a 09 73 74 72 ty = 571; ...str
10a0: 69 6e 67 20 5f 20 3d 20 22 59 45 53 22 3b 20 0d ing _ = "YES"; .
10b0: 0a 45 4e 44 0d 0a 43 41 53 45 28 34 29 0d 0a 09 .END..CASE(4)...
10c0: 69 6e 74 20 78 5f 5b 5d 20 3d 20 7b 31 2c 20 32 int x_[] = {1, 2
10d0: 2c 20 33 2c 20 34 2c 20 35 2c 20 36 2c 20 37 2c , 3, 4, 5, 6, 7,
10e0: 20 38 2c 20 39 2c 20 31 30 2c 20 31 31 2c 20 31 8, 9, 10, 11, 1
10f0: 32 2c 20 31 33 2c 20 31 34 2c 20 31 35 2c 20 31 2, 13, 14, 15, 1
1100: 36 2c 20 31 37 2c 20 31 38 2c 20 31 39 2c 20 32 6, 17, 18, 19, 2
1110: 30 7d 3b 0d 0a 09 20 20 76 65 63 74 6f 72 20 3c 0};... vector <
1120: 69 6e 74 3e 20 78 28 78 5f 2c 20 78 5f 2b 73 69 int> x(x_, x_+si
1130: 7a 65 6f 66 28 78 5f 29 2f 73 69 7a 65 6f 66 28 zeof(x_)/sizeof(
1140: 2a 78 5f 29 29 3b 20 0d 0a 09 69 6e 74 20 79 5f *x_)); ...int y_
1150: 5b 5d 20 3d 20 7b 31 2c 20 32 2c 20 33 2c 20 34 [] = {1, 2, 3, 4
1160: 2c 20 35 2c 20 36 2c 20 37 2c 20 38 2c 20 39 2c , 5, 6, 7, 8, 9,
1170: 20 31 30 2c 20 31 31 2c 20 31 32 2c 20 31 33 2c 10, 11, 12, 13,
1180: 20 31 34 2c 20 31 35 2c 20 31 36 2c 20 31 37 2c 14, 15, 16, 17,
1190: 20 31 38 2c 20 31 39 2c 20 32 30 7d 3b 0d 0a 09 18, 19, 20};...
11a0: 20 20 76 65 63 74 6f 72 20 3c 69 6e 74 3e 20 79 vector <int> y
11b0: 28 79 5f 2c 20 79 5f 2b 73 69 7a 65 6f 66 28 79 (y_, y_+sizeof(y
11c0: 5f 29 2f 73 69 7a 65 6f 66 28 2a 79 5f 29 29 3b _)/sizeof(*y_));
11d0: 20 0d 0a 09 69 6e 74 20 72 5f 5b 5d 20 3d 20 7b ...int r_[] = {
11e0: 32 2c 20 32 2c 20 32 2c 20 32 2c 20 32 2c 20 32 2, 2, 2, 2, 2, 2
11f0: 2c 20 32 2c 20 32 2c 20 32 2c 20 32 2c 20 32 2c , 2, 2, 2, 2, 2,
1200: 20 32 2c 20 32 2c 20 32 2c 20 32 2c 20 32 2c 20 2, 2, 2, 2, 2,
1210: 32 2c 20 32 2c 20 32 2c 20 32 7d 3b 0d 0a 09 20 2, 2, 2, 2};...
1220: 20 76 65 63 74 6f 72 20 3c 69 6e 74 3e 20 72 28 vector <int> r(
1230: 72 5f 2c 20 72 5f 2b 73 69 7a 65 6f 66 28 72 5f r_, r_+sizeof(r_
1240: 29 2f 73 69 7a 65 6f 66 28 2a 72 5f 29 29 3b 20 )/sizeof(*r_));
1250: 0d 0a 09 69 6e 74 20 73 78 20 3d 20 32 3b 20 0d ...int sx = 2; .
1260: 0a 09 69 6e 74 20 73 79 20 3d 20 32 3b 20 0d 0a ..int sy = 2; ..
1270: 09 69 6e 74 20 74 78 20 3d 20 31 39 3b 20 0d 0a .int tx = 19; ..
1280: 09 69 6e 74 20 74 79 20 3d 20 31 39 3b 20 0d 0a .int ty = 19; ..
1290: 09 73 74 72 69 6e 67 20 5f 20 3d 20 22 59 45 53 .string _ = "YES
12a0: 22 3b 20 0d 0a 45 4e 44 0d 0a 43 41 53 45 28 35 "; ..END..CASE(5
12b0: 29 0d 0a 09 69 6e 74 20 78 5f 5b 5d 20 3d 20 7b )...int x_[] = {
12c0: 31 2c 20 32 2c 20 33 2c 20 34 2c 20 35 2c 20 36 1, 2, 3, 4, 5, 6
12d0: 2c 20 37 2c 20 38 2c 20 39 2c 20 31 30 2c 20 31 , 7, 8, 9, 10, 1
12e0: 31 2c 20 31 32 2c 20 31 33 2c 20 31 34 2c 20 31 1, 12, 13, 14, 1
12f0: 35 2c 20 31 36 2c 20 31 37 2c 20 31 38 2c 20 31 5, 16, 17, 18, 1
1300: 39 2c 20 32 30 7d 3b 0d 0a 09 20 20 76 65 63 74 9, 20};... vect
1310: 6f 72 20 3c 69 6e 74 3e 20 78 28 78 5f 2c 20 78 or <int> x(x_, x
1320: 5f 2b 73 69 7a 65 6f 66 28 78 5f 29 2f 73 69 7a _+sizeof(x_)/siz
1330: 65 6f 66 28 2a 78 5f 29 29 3b 20 0d 0a 09 69 6e eof(*x_)); ...in
1340: 74 20 79 5f 5b 5d 20 3d 20 7b 31 2c 20 32 2c 20 t y_[] = {1, 2,
1350: 33 2c 20 34 2c 20 35 2c 20 36 2c 20 37 2c 20 38 3, 4, 5, 6, 7, 8
1360: 2c 20 39 2c 20 31 30 2c 20 31 31 2c 20 31 32 2c , 9, 10, 11, 12,
1370: 20 31 33 2c 20 31 34 2c 20 31 35 2c 20 31 36 2c 13, 14, 15, 16,
1380: 20 31 37 2c 20 31 38 2c 20 31 39 2c 20 32 30 7d 17, 18, 19, 20}
1390: 3b 0d 0a 09 20 20 76 65 63 74 6f 72 20 3c 69 6e ;... vector <in
13a0: 74 3e 20 79 28 79 5f 2c 20 79 5f 2b 73 69 7a 65 t> y(y_, y_+size
13b0: 6f 66 28 79 5f 29 2f 73 69 7a 65 6f 66 28 2a 79 of(y_)/sizeof(*y
13c0: 5f 29 29 3b 20 0d 0a 09 69 6e 74 20 72 5f 5b 5d _)); ...int r_[]
13d0: 20 3d 20 7b 31 2c 20 31 2c 20 31 2c 20 31 2c 20 = {1, 1, 1, 1,
13e0: 31 2c 20 31 2c 20 31 2c 20 31 2c 20 31 2c 20 31 1, 1, 1, 1, 1, 1
13f0: 2c 20 31 2c 20 31 2c 20 31 2c 20 31 2c 20 31 2c , 1, 1, 1, 1, 1,
1400: 20 31 2c 20 31 2c 20 31 2c 20 31 2c 20 31 7d 3b 1, 1, 1, 1, 1};
1410: 0d 0a 09 20 20 76 65 63 74 6f 72 20 3c 69 6e 74 ... vector <int
1420: 3e 20 72 28 72 5f 2c 20 72 5f 2b 73 69 7a 65 6f > r(r_, r_+sizeo
1430: 66 28 72 5f 29 2f 73 69 7a 65 6f 66 28 2a 72 5f f(r_)/sizeof(*r_
1440: 29 29 3b 20 0d 0a 09 69 6e 74 20 73 78 20 3d 20 )); ...int sx =
1450: 32 3b 20 0d 0a 09 69 6e 74 20 73 79 20 3d 20 32 2; ...int sy = 2
1460: 3b 20 0d 0a 09 69 6e 74 20 74 78 20 3d 20 31 39 ; ...int tx = 19
1470: 3b 20 0d 0a 09 69 6e 74 20 74 79 20 3d 20 31 39 ; ...int ty = 19
1480: 3b 20 0d 0a 09 73 74 72 69 6e 67 20 5f 20 3d 20 ; ...string _ =
1490: 22 4e 4f 22 3b 20 0d 0a 45 4e 44 0d 0a 2f 2a 0d "NO"; ..END../*.
14a0: 0a 43 41 53 45 28 36 29 0d 0a 09 69 6e 74 20 78 .CASE(6)...int x
14b0: 5f 5b 5d 20 3d 20 3b 0d 0a 09 20 20 76 65 63 74 _[] = ;... vect
14c0: 6f 72 20 3c 69 6e 74 3e 20 78 28 78 5f 2c 20 78 or <int> x(x_, x
14d0: 5f 2b 73 69 7a 65 6f 66 28 78 5f 29 2f 73 69 7a _+sizeof(x_)/siz
14e0: 65 6f 66 28 2a 78 5f 29 29 3b 20 0d 0a 09 69 6e eof(*x_)); ...in
14f0: 74 20 79 5f 5b 5d 20 3d 20 3b 0d 0a 09 20 20 76 t y_[] = ;... v
1500: 65 63 74 6f 72 20 3c 69 6e 74 3e 20 79 28 79 5f ector <int> y(y_
1510: 2c 20 79 5f 2b 73 69 7a 65 6f 66 28 79 5f 29 2f , y_+sizeof(y_)/
1520: 73 69 7a 65 6f 66 28 2a 79 5f 29 29 3b 20 0d 0a sizeof(*y_)); ..
1530: 09 69 6e 74 20 72 5f 5b 5d 20 3d 20 3b 0d 0a 09 .int r_[] = ;...
1540: 20 20 76 65 63 74 6f 72 20 3c 69 6e 74 3e 20 72 vector <int> r
1550: 28 72 5f 2c 20 72 5f 2b 73 69 7a 65 6f 66 28 72 (r_, r_+sizeof(r
1560: 5f 29 2f 73 69 7a 65 6f 66 28 2a 72 5f 29 29 3b _)/sizeof(*r_));
1570: 20 0d 0a 09 69 6e 74 20 73 78 20 3d 20 3b 20 0d ...int sx = ; .
1580: 0a 09 69 6e 74 20 73 79 20 3d 20 3b 20 0d 0a 09 ..int sy = ; ...
1590: 69 6e 74 20 74 78 20 3d 20 3b 20 0d 0a 09 69 6e int tx = ; ...in
15a0: 74 20 74 79 20 3d 20 3b 20 0d 0a 09 73 74 72 69 t ty = ; ...stri
15b0: 6e 67 20 5f 20 3d 20 3b 20 0d 0a 45 4e 44 0d 0a ng _ = ; ..END..
15c0: 43 41 53 45 28 37 29 0d 0a 09 69 6e 74 20 78 5f CASE(7)...int x_
15d0: 5b 5d 20 3d 20 3b 0d 0a 09 20 20 76 65 63 74 6f [] = ;... vecto
15e0: 72 20 3c 69 6e 74 3e 20 78 28 78 5f 2c 20 78 5f r <int> x(x_, x_
15f0: 2b 73 69 7a 65 6f 66 28 78 5f 29 2f 73 69 7a 65 +sizeof(x_)/size
1600: 6f 66 28 2a 78 5f 29 29 3b 20 0d 0a 09 69 6e 74 of(*x_)); ...int
1610: 20 79 5f 5b 5d 20 3d 20 3b 0d 0a 09 20 20 76 65 y_[] = ;... ve
1620: 63 74 6f 72 20 3c 69 6e 74 3e 20 79 28 79 5f 2c ctor <int> y(y_,
1630: 20 79 5f 2b 73 69 7a 65 6f 66 28 79 5f 29 2f 73 y_+sizeof(y_)/s
1640: 69 7a 65 6f 66 28 2a 79 5f 29 29 3b 20 0d 0a 09 izeof(*y_)); ...
1650: 69 6e 74 20 72 5f 5b 5d 20 3d 20 3b 0d 0a 09 20 int r_[] = ;...
1660: 20 76 65 63 74 6f 72 20 3c 69 6e 74 3e 20 72 28 vector <int> r(
1670: 72 5f 2c 20 72 5f 2b 73 69 7a 65 6f 66 28 72 5f r_, r_+sizeof(r_
1680: 29 2f 73 69 7a 65 6f 66 28 2a 72 5f 29 29 3b 20 )/sizeof(*r_));
1690: 0d 0a 09 69 6e 74 20 73 78 20 3d 20 3b 20 0d 0a ...int sx = ; ..
16a0: 09 69 6e 74 20 73 79 20 3d 20 3b 20 0d 0a 09 69 .int sy = ; ...i
16b0: 6e 74 20 74 78 20 3d 20 3b 20 0d 0a 09 69 6e 74 nt tx = ; ...int
16c0: 20 74 79 20 3d 20 3b 20 0d 0a 09 73 74 72 69 6e ty = ; ...strin
16d0: 67 20 5f 20 3d 20 3b 20 0d 0a 45 4e 44 0d 0a 2a g _ = ; ..END..*
16e0: 2f 0d 0a 7d 0d 0a 2f 2f 20 45 4e 44 20 43 55 54 /..}..// END CUT
16f0: 20 48 45 52 45 0d 0a HERE..