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 64 6f 75 62 6c 65 20 6f CMP;....double o
01a0: 75 74 65 72 5f 70 72 6f 64 28 63 6f 6e 73 74 20 uter_prod(const
01b0: 43 4d 50 26 20 61 2c 20 63 6f 6e 73 74 20 43 4d CMP& a, const CM
01c0: 50 26 20 62 29 20 7b 20 72 65 74 75 72 6e 20 69 P& b) { return i
01d0: 6d 61 67 28 63 6f 6e 6a 28 61 29 2a 62 29 3b 20 mag(conj(a)*b);
01e0: 7d 0d 0a 64 6f 75 62 6c 65 20 69 6e 6e 65 72 5f }..double inner_
01f0: 70 72 6f 64 28 63 6f 6e 73 74 20 43 4d 50 26 20 prod(const CMP&
0200: 61 2c 20 63 6f 6e 73 74 20 43 4d 50 26 20 62 29 a, const CMP& b)
0210: 20 7b 20 72 65 74 75 72 6e 20 72 65 61 6c 28 63 { return real(c
0220: 6f 6e 6a 28 61 29 2a 62 29 3b 20 7d 0d 0a 0d 0a onj(a)*b); }....
0230: 69 6e 74 20 63 63 77 28 63 6f 6e 73 74 20 43 4d int ccw(const CM
0240: 50 26 20 61 2c 20 43 4d 50 20 62 2c 20 43 4d 50 P& a, CMP b, CMP
0250: 20 63 29 20 7b 0d 0a 09 62 20 2d 3d 20 61 3b 20 c) {...b -= a;
0260: 63 20 2d 3d 20 61 3b 0d 0a 09 69 66 28 20 6f 75 c -= a;...if( ou
0270: 74 65 72 5f 70 72 6f 64 28 62 2c 63 29 20 3e 20 ter_prod(b,c) >
0280: 30 20 29 20 72 65 74 75 72 6e 20 2b 31 3b 20 2f 0 ) return +1; /
0290: 2f 20 63 6f 75 6e 74 65 72 20 63 6c 6f 63 6b 77 / counter clockw
02a0: 69 73 65 0d 0a 09 69 66 28 20 6f 75 74 65 72 5f ise...if( outer_
02b0: 70 72 6f 64 28 62 2c 63 29 20 3c 20 30 20 29 20 prod(b,c) < 0 )
02c0: 72 65 74 75 72 6e 20 2d 31 3b 20 2f 2f 20 63 6c return -1; // cl
02d0: 6f 63 6b 77 69 73 65 0d 0a 09 69 66 28 20 69 6e ockwise...if( in
02e0: 6e 65 72 5f 70 72 6f 64 28 62 2c 63 29 20 3c 20 ner_prod(b,c) <
02f0: 30 20 29 20 72 65 74 75 72 6e 20 2b 32 3b 20 2f 0 ) return +2; /
0300: 2f 20 63 2d 2d 61 2d 2d 62 20 6f 6e 20 6c 69 6e / c--a--b on lin
0310: 65 0d 0a 09 69 66 28 20 6e 6f 72 6d 28 62 29 20 e...if( norm(b)
0320: 3c 20 6e 6f 72 6d 28 63 29 20 29 20 20 20 72 65 < norm(c) ) re
0330: 74 75 72 6e 20 2d 32 3b 20 2f 2f 20 61 2d 2d 62 turn -2; // a--b
0340: 2d 2d 63 20 6f 6e 20 6c 69 6e 65 0d 0a 09 72 65 --c on line...re
0350: 74 75 72 6e 20 30 3b 0d 0a 7d 0d 0a 0d 0a 62 6f turn 0;..}....bo
0360: 6f 6c 20 62 79 58 28 20 63 6f 6e 73 74 20 43 4d ol byX( const CM
0370: 50 26 20 61 2c 20 63 6f 6e 73 74 20 43 4d 50 26 P& a, const CMP&
0380: 20 62 20 29 20 7b 0d 0a 09 69 66 28 20 61 2e 72 b ) {...if( a.r
0390: 65 61 6c 28 29 20 21 3d 20 62 2e 72 65 61 6c 28 eal() != b.real(
03a0: 29 20 29 0d 0a 09 09 72 65 74 75 72 6e 20 61 2e ) )....return a.
03b0: 72 65 61 6c 28 29 20 3c 20 62 2e 72 65 61 6c 28 real() < b.real(
03c0: 29 3b 0d 0a 09 72 65 74 75 72 6e 20 61 2e 69 6d );...return a.im
03d0: 61 67 28 29 20 3c 20 62 2e 69 6d 61 67 28 29 3b ag() < b.imag();
03e0: 0d 0a 7d 0d 0a 0d 0a 76 65 63 74 6f 72 3c 43 4d ..}....vector<CM
03f0: 50 3e 20 63 6f 6e 76 65 78 5f 68 75 6c 6c 28 20 P> convex_hull(
0400: 76 65 63 74 6f 72 3c 43 4d 50 3e 20 70 20 29 0d vector<CMP> p ).
0410: 0a 7b 0d 0a 09 23 64 65 66 69 6e 65 20 49 53 5f .{...#define IS_
0420: 52 49 47 48 54 20 3c 30 20 20 20 2f 2f 20 73 6b RIGHT <0 // sk
0430: 69 70 20 6f 6e 2d 6c 69 6e 65 20 76 65 72 74 73 ip on-line verts
0440: 0d 0a 09 2f 2f 23 64 65 66 69 6e 65 20 49 53 5f ...//#define IS_
0450: 52 49 47 48 54 20 3d 3d 2d 31 20 2f 2f 20 74 61 RIGHT ==-1 // ta
0460: 6b 65 20 61 6c 6c 0d 0a 0d 0a 09 73 6f 72 74 28 ke all.....sort(
0470: 70 2e 62 65 67 69 6e 28 29 2c 20 70 2e 65 6e 64 p.begin(), p.end
0480: 28 29 2c 20 26 62 79 58 29 3b 0d 0a 0d 0a 09 76 (), &byX);.....v
0490: 65 63 74 6f 72 3c 43 4d 50 3e 20 61 6e 73 3b 0d ector<CMP> ans;.
04a0: 0a 09 66 6f 72 28 69 6e 74 20 69 3d 30 3b 20 69 ..for(int i=0; i
04b0: 3c 70 2e 73 69 7a 65 28 29 3b 20 61 6e 73 2e 70 <p.size(); ans.p
04c0: 75 73 68 5f 62 61 63 6b 28 70 5b 69 2b 2b 5d 29 ush_back(p[i++])
04d0: 29 20 2f 2f 20 6c 65 66 74 2d 74 6f 2d 72 69 67 ) // left-to-rig
04e0: 68 74 0d 0a 09 09 77 68 69 6c 65 28 20 61 6e 73 ht....while( ans
04f0: 2e 73 69 7a 65 28 29 3e 3d 32 20 26 26 20 63 63 .size()>=2 && cc
0500: 77 28 61 6e 73 5b 61 6e 73 2e 73 69 7a 65 28 29 w(ans[ans.size()
0510: 2d 32 5d 2c 20 61 6e 73 5b 61 6e 73 2e 73 69 7a -2], ans[ans.siz
0520: 65 28 29 2d 31 5d 2c 20 70 5b 69 5d 29 20 49 53 e()-1], p[i]) IS
0530: 5f 52 49 47 48 54 20 29 0d 0a 09 09 09 61 6e 73 _RIGHT ).....ans
0540: 2e 70 6f 70 5f 62 61 63 6b 28 29 3b 0d 0a 09 69 .pop_back();...i
0550: 66 28 20 61 6e 73 2e 73 69 7a 65 28 29 20 3d 3d f( ans.size() ==
0560: 20 70 2e 73 69 7a 65 28 29 20 29 0d 0a 09 09 72 p.size() )....r
0570: 65 74 75 72 6e 20 61 6e 73 3b 0d 0a 09 66 6f 72 eturn ans;...for
0580: 28 69 6e 74 20 69 3d 70 2e 73 69 7a 65 28 29 2d (int i=p.size()-
0590: 32 3b 20 69 3e 3d 30 3b 20 61 6e 73 2e 70 75 73 2; i>=0; ans.pus
05a0: 68 5f 62 61 63 6b 28 70 5b 69 2d 2d 5d 29 29 20 h_back(p[i--]))
05b0: 2f 2f 20 72 69 67 68 74 2d 74 6f 2d 6c 65 66 74 // right-to-left
05c0: 0d 0a 09 09 77 68 69 6c 65 28 20 61 6e 73 2e 73 ....while( ans.s
05d0: 69 7a 65 28 29 3e 3d 32 20 26 26 20 63 63 77 28 ize()>=2 && ccw(
05e0: 61 6e 73 5b 61 6e 73 2e 73 69 7a 65 28 29 2d 32 ans[ans.size()-2
05f0: 5d 2c 20 61 6e 73 5b 61 6e 73 2e 73 69 7a 65 28 ], ans[ans.size(
0600: 29 2d 31 5d 2c 20 70 5b 69 5d 29 20 49 53 5f 52 )-1], p[i]) IS_R
0610: 49 47 48 54 20 29 0d 0a 09 09 09 61 6e 73 2e 70 IGHT ).....ans.p
0620: 6f 70 5f 62 61 63 6b 28 29 3b 0d 0a 09 61 6e 73 op_back();...ans
0630: 2e 70 6f 70 5f 62 61 63 6b 28 29 3b 0d 0a 09 72 .pop_back();...r
0640: 65 74 75 72 6e 20 61 6e 73 3b 0d 0a 7d 0d 0a 0d eturn ans;..}...
0650: 0a 64 6f 75 62 6c 65 20 61 72 65 61 28 20 63 6f .double area( co
0660: 6e 73 74 20 76 65 63 74 6f 72 3c 43 4d 50 3e 26 nst vector<CMP>&
0670: 20 71 20 29 0d 0a 7b 0d 0a 09 64 6f 75 62 6c 65 q )..{...double
0680: 20 61 20 3d 20 30 2e 30 3b 0d 0a 0d 0a 09 43 4d a = 0.0;.....CM
0690: 50 20 6f 20 3d 20 71 5b 30 5d 3b 0d 0a 09 66 6f P o = q[0];...fo
06a0: 72 28 69 6e 74 20 69 3d 31 3b 20 69 2b 31 3c 71 r(int i=1; i+1<q
06b0: 2e 73 69 7a 65 28 29 3b 20 2b 2b 69 29 0d 0a 09 .size(); ++i)...
06c0: 09 61 20 2b 3d 20 6f 75 74 65 72 5f 70 72 6f 64 .a += outer_prod
06d0: 28 71 5b 69 5d 2d 6f 2c 20 71 5b 69 2b 31 5d 2d (q[i]-o, q[i+1]-
06e0: 6f 29 3b 0d 0a 09 72 65 74 75 72 6e 20 61 62 73 o);...return abs
06f0: 28 61 29 2f 32 3b 0d 0a 7d 0d 0a 0d 0a 63 6c 61 (a)/2;..}....cla
0700: 73 73 20 42 61 74 6d 61 6e 41 6e 64 52 6f 62 69 ss BatmanAndRobi
0710: 6e 20 7b 20 70 75 62 6c 69 63 3a 0d 0a 09 64 6f n { public:...do
0720: 75 62 6c 65 20 6d 69 6e 41 72 65 61 28 76 65 63 uble minArea(vec
0730: 74 6f 72 20 3c 69 6e 74 3e 20 78 2c 20 76 65 63 tor <int> x, vec
0740: 74 6f 72 20 3c 69 6e 74 3e 20 79 29 20 0d 0a 09 tor <int> y) ...
0750: 7b 0d 0a 09 09 69 6e 74 20 4e 20 3d 20 78 2e 73 {....int N = x.s
0760: 69 7a 65 28 29 3b 0d 0a 09 09 76 65 63 74 6f 72 ize();....vector
0770: 3c 43 4d 50 3e 20 70 3b 0d 0a 09 09 66 6f 72 28 <CMP> p;....for(
0780: 69 6e 74 20 69 3d 30 3b 20 69 3c 4e 3b 20 2b 2b int i=0; i<N; ++
0790: 69 29 0d 0a 09 09 09 70 2e 70 75 73 68 5f 62 61 i).....p.push_ba
07a0: 63 6b 28 43 4d 50 28 78 5b 69 5d 2c 79 5b 69 5d ck(CMP(x[i],y[i]
07b0: 29 29 3b 0d 0a 0d 0a 09 09 63 6f 6e 73 74 20 64 ));......const d
07c0: 6f 75 62 6c 65 20 65 70 73 20 3d 20 31 65 2d 36 ouble eps = 1e-6
07d0: 3b 0d 0a 09 09 43 4d 50 20 64 69 66 66 5b 5d 20 ;....CMP diff[]
07e0: 3d 20 7b 43 4d 50 28 65 70 73 2c 30 29 2c 20 43 = {CMP(eps,0), C
07f0: 4d 50 28 30 2c 65 70 73 29 2c 20 43 4d 50 28 2d MP(0,eps), CMP(-
0800: 65 70 73 2c 30 29 2c 20 43 4d 50 28 30 2c 2d 65 eps,0), CMP(0,-e
0810: 70 73 29 7d 3b 0d 0a 09 09 64 6f 75 62 6c 65 20 ps)};....double
0820: 61 6e 73 77 65 72 20 3d 20 61 72 65 61 28 63 6f answer = area(co
0830: 6e 76 65 78 5f 68 75 6c 6c 28 70 29 29 3b 0d 0a nvex_hull(p));..
0840: 09 09 66 6f 72 28 69 6e 74 20 69 3d 30 3b 20 69 ..for(int i=0; i
0850: 3c 4e 3b 20 2b 2b 69 29 0d 0a 09 09 09 66 6f 72 <N; ++i).....for
0860: 28 69 6e 74 20 6a 3d 69 2b 31 3b 20 6a 3c 4e 3b (int j=i+1; j<N;
0870: 20 2b 2b 6a 29 20 7b 0d 0a 09 09 09 09 66 6f 72 ++j) {......for
0880: 28 69 6e 74 20 64 69 3d 30 3b 20 64 69 3c 34 3b (int di=0; di<4;
0890: 20 2b 2b 64 69 29 0d 0a 09 09 09 09 09 66 6f 72 ++di).......for
08a0: 28 69 6e 74 20 64 6a 3d 30 3b 20 64 6a 3c 34 3b (int dj=0; dj<4;
08b0: 20 2b 2b 64 6a 29 20 7b 0d 0a 09 09 09 09 09 09 ++dj) {........
08c0: 76 65 63 74 6f 72 3c 43 4d 50 3e 20 61 20 3d 20 vector<CMP> a =
08d0: 6c 65 66 74 5f 6f 66 28 70 2c 20 70 5b 69 5d 2b left_of(p, p[i]+
08e0: 64 69 66 66 5b 64 69 5d 2c 20 70 5b 6a 5d 2b 64 diff[di], p[j]+d
08f0: 69 66 66 5b 64 6a 5d 29 3b 0d 0a 09 09 09 09 09 iff[dj]);.......
0900: 09 76 65 63 74 6f 72 3c 43 4d 50 3e 20 62 20 3d .vector<CMP> b =
0910: 20 72 69 67 68 74 5f 6f 66 28 70 2c 20 70 5b 69 right_of(p, p[i
0920: 5d 2b 64 69 66 66 5b 64 69 5d 2c 20 70 5b 6a 5d ]+diff[di], p[j]
0930: 2b 64 69 66 66 5b 64 6a 5d 29 3b 0d 0a 09 09 09 +diff[dj]);.....
0940: 09 09 09 64 6f 75 62 6c 65 20 61 61 20 3d 20 61 ...double aa = a
0950: 2e 73 69 7a 65 28 29 3c 3d 32 20 3f 20 30 20 3a .size()<=2 ? 0 :
0960: 20 61 72 65 61 28 63 6f 6e 76 65 78 5f 68 75 6c area(convex_hul
0970: 6c 28 61 29 29 3b 0d 0a 09 09 09 09 09 09 64 6f l(a));........do
0980: 75 62 6c 65 20 62 62 20 3d 20 62 2e 73 69 7a 65 uble bb = b.size
0990: 28 29 3c 3d 32 20 3f 20 30 20 3a 20 61 72 65 61 ()<=2 ? 0 : area
09a0: 28 63 6f 6e 76 65 78 5f 68 75 6c 6c 28 62 29 29 (convex_hull(b))
09b0: 3b 0d 0a 09 09 09 09 09 09 61 6e 73 77 65 72 20 ;........answer
09c0: 3d 20 6d 69 6e 28 61 6e 73 77 65 72 2c 20 6d 61 = min(answer, ma
09d0: 78 28 61 61 2c 62 62 29 29 3b 0d 0a 09 09 09 09 x(aa,bb));......
09e0: 09 7d 0d 0a 09 09 09 7d 0d 0a 09 09 72 65 74 75 .}.....}....retu
09f0: 72 6e 20 61 6e 73 77 65 72 3b 0d 0a 09 7d 0d 0a rn answer;...}..
0a00: 0d 0a 09 76 65 63 74 6f 72 3c 43 4d 50 3e 20 6c ...vector<CMP> l
0a10: 65 66 74 5f 6f 66 28 63 6f 6e 73 74 20 76 65 63 eft_of(const vec
0a20: 74 6f 72 3c 43 4d 50 3e 26 20 70 2c 20 63 6f 6e tor<CMP>& p, con
0a30: 73 74 20 43 4d 50 26 20 6f 2c 20 43 4d 50 20 76 st CMP& o, CMP v
0a40: 29 0d 0a 09 7b 0d 0a 09 09 76 20 2d 3d 20 6f 3b )...{....v -= o;
0a50: 0d 0a 09 09 76 65 63 74 6f 72 3c 43 4d 50 3e 20 ....vector<CMP>
0a60: 72 3b 0d 0a 09 09 66 6f 72 28 69 6e 74 20 69 3d r;....for(int i=
0a70: 30 3b 20 69 3c 70 2e 73 69 7a 65 28 29 3b 20 2b 0; i<p.size(); +
0a80: 2b 69 29 0d 0a 09 09 09 69 66 28 20 69 73 5f 6c +i).....if( is_l
0a90: 65 66 74 28 70 5b 69 5d 2d 6f 2c 20 76 29 20 29 eft(p[i]-o, v) )
0aa0: 0d 0a 09 09 09 09 72 2e 70 75 73 68 5f 62 61 63 ......r.push_bac
0ab0: 6b 28 70 5b 69 5d 29 3b 0d 0a 09 09 72 65 74 75 k(p[i]);....retu
0ac0: 72 6e 20 72 3b 0d 0a 09 7d 0d 0a 09 76 65 63 74 rn r;...}...vect
0ad0: 6f 72 3c 43 4d 50 3e 20 72 69 67 68 74 5f 6f 66 or<CMP> right_of
0ae0: 28 63 6f 6e 73 74 20 76 65 63 74 6f 72 3c 43 4d (const vector<CM
0af0: 50 3e 26 20 70 2c 20 63 6f 6e 73 74 20 43 4d 50 P>& p, const CMP
0b00: 26 20 6f 2c 20 43 4d 50 20 76 29 0d 0a 09 7b 0d & o, CMP v)...{.
0b10: 0a 09 09 76 20 2d 3d 20 6f 3b 0d 0a 09 09 76 65 ...v -= o;....ve
0b20: 63 74 6f 72 3c 43 4d 50 3e 20 72 3b 0d 0a 09 09 ctor<CMP> r;....
0b30: 66 6f 72 28 69 6e 74 20 69 3d 30 3b 20 69 3c 70 for(int i=0; i<p
0b40: 2e 73 69 7a 65 28 29 3b 20 2b 2b 69 29 0d 0a 09 .size(); ++i)...
0b50: 09 09 69 66 28 20 21 69 73 5f 6c 65 66 74 28 70 ..if( !is_left(p
0b60: 5b 69 5d 2d 6f 2c 20 76 29 20 29 0d 0a 09 09 09 [i]-o, v) ).....
0b70: 09 72 2e 70 75 73 68 5f 62 61 63 6b 28 70 5b 69 .r.push_back(p[i
0b80: 5d 29 3b 0d 0a 09 09 72 65 74 75 72 6e 20 72 3b ]);....return r;
0b90: 0d 0a 09 7d 0d 0a 09 62 6f 6f 6c 20 69 73 5f 6c ...}...bool is_l
0ba0: 65 66 74 28 63 6f 6e 73 74 20 43 4d 50 26 20 70 eft(const CMP& p
0bb0: 2c 20 63 6f 6e 73 74 20 43 4d 50 26 20 76 29 0d , const CMP& v).
0bc0: 0a 09 7b 0d 0a 09 09 72 65 74 75 72 6e 20 61 72 ..{....return ar
0bd0: 67 28 70 2f 76 29 3e 30 3b 0d 0a 09 7d 0d 0a 7d g(p/v)>0;...}..}
0be0: 3b 0d 0a 0d 0a 2f 2f 20 42 45 47 49 4e 20 43 55 ;....// BEGIN CU
0bf0: 54 20 48 45 52 45 0d 0a 23 69 6e 63 6c 75 64 65 T HERE..#include
0c00: 20 3c 63 74 69 6d 65 3e 0d 0a 64 6f 75 62 6c 65 <ctime>..double
0c10: 20 73 74 61 72 74 5f 74 69 6d 65 3b 20 73 74 72 start_time; str
0c20: 69 6e 67 20 74 69 6d 65 72 28 29 0d 0a 20 7b 20 ing timer().. {
0c30: 6f 73 74 72 69 6e 67 73 74 72 65 61 6d 20 6f 73 ostringstream os
0c40: 3b 20 6f 73 20 3c 3c 20 22 20 28 22 20 3c 3c 20 ; os << " (" <<
0c50: 69 6e 74 28 28 63 6c 6f 63 6b 28 29 2d 73 74 61 int((clock()-sta
0c60: 72 74 5f 74 69 6d 65 29 2f 43 4c 4f 43 4b 53 5f rt_time)/CLOCKS_
0c70: 50 45 52 5f 53 45 43 2a 31 30 30 30 29 20 3c 3c PER_SEC*1000) <<
0c80: 20 22 20 6d 73 65 63 29 22 3b 20 72 65 74 75 72 " msec)"; retur
0c90: 6e 20 6f 73 2e 73 74 72 28 29 3b 20 7d 0d 0a 74 n os.str(); }..t
0ca0: 65 6d 70 6c 61 74 65 3c 74 79 70 65 6e 61 6d 65 emplate<typename
0cb0: 20 54 3e 20 6f 73 74 72 65 61 6d 26 20 6f 70 65 T> ostream& ope
0cc0: 72 61 74 6f 72 3c 3c 28 6f 73 74 72 65 61 6d 26 rator<<(ostream&
0cd0: 20 6f 73 2c 20 63 6f 6e 73 74 20 76 65 63 74 6f os, const vecto
0ce0: 72 3c 54 3e 26 20 76 29 0d 0a 20 7b 20 6f 73 20 r<T>& v).. { os
0cf0: 3c 3c 20 22 7b 20 22 3b 0d 0a 20 20 20 66 6f 72 << "{ ";.. for
0d00: 28 74 79 70 65 6e 61 6d 65 20 76 65 63 74 6f 72 (typename vector
0d10: 3c 54 3e 3a 3a 63 6f 6e 73 74 5f 69 74 65 72 61 <T>::const_itera
0d20: 74 6f 72 20 69 74 3d 76 2e 62 65 67 69 6e 28 29 tor it=v.begin()
0d30: 3b 20 69 74 21 3d 76 2e 65 6e 64 28 29 3b 20 2b ; it!=v.end(); +
0d40: 2b 69 74 29 0d 0a 20 20 20 6f 73 20 3c 3c 20 27 +it).. os << '
0d50: 5c 22 27 20 3c 3c 20 2a 69 74 20 3c 3c 20 27 5c \"' << *it << '\
0d60: 22 27 20 3c 3c 20 28 69 74 2b 31 3d 3d 76 2e 65 "' << (it+1==v.e
0d70: 6e 64 28 29 20 3f 20 22 22 20 3a 20 22 2c 20 22 nd() ? "" : ", "
0d80: 29 3b 20 6f 73 20 3c 3c 20 22 20 7d 22 3b 20 72 ); os << " }"; r
0d90: 65 74 75 72 6e 20 6f 73 3b 20 7d 0d 0a 76 6f 69 eturn os; }..voi
0da0: 64 20 76 65 72 69 66 79 5f 63 61 73 65 28 63 6f d verify_case(co
0db0: 6e 73 74 20 64 6f 75 62 6c 65 26 20 45 78 70 65 nst double& Expe
0dc0: 63 74 65 64 2c 20 63 6f 6e 73 74 20 64 6f 75 62 cted, const doub
0dd0: 6c 65 26 20 52 65 63 65 69 76 65 64 29 20 7b 0d le& Received) {.
0de0: 0a 20 62 6f 6f 6c 20 6f 6b 20 3d 20 28 61 62 73 . bool ok = (abs
0df0: 28 45 78 70 65 63 74 65 64 20 2d 20 52 65 63 65 (Expected - Rece
0e00: 69 76 65 64 29 20 3c 20 31 65 2d 39 29 3b 0d 0a ived) < 1e-9);..
0e10: 20 69 66 28 6f 6b 29 20 63 65 72 72 20 3c 3c 20 if(ok) cerr <<
0e20: 22 50 41 53 53 45 44 22 20 3c 3c 20 74 69 6d 65 "PASSED" << time
0e30: 72 28 29 20 3c 3c 20 65 6e 64 6c 3b 20 20 65 6c r() << endl; el
0e40: 73 65 20 7b 20 63 65 72 72 20 3c 3c 20 22 46 41 se { cerr << "FA
0e50: 49 4c 45 44 22 20 3c 3c 20 74 69 6d 65 72 28 29 ILED" << timer()
0e60: 20 3c 3c 20 65 6e 64 6c 3b 0d 0a 20 63 65 72 72 << endl;.. cerr
0e70: 20 3c 3c 20 22 5c 74 6f 3a 20 5c 22 22 20 3c 3c << "\to: \"" <<
0e80: 20 45 78 70 65 63 74 65 64 20 3c 3c 20 27 5c 22 Expected << '\"
0e90: 27 20 3c 3c 20 65 6e 64 6c 20 3c 3c 20 22 5c 74 ' << endl << "\t
0ea0: 78 3a 20 5c 22 22 20 3c 3c 20 52 65 63 65 69 76 x: \"" << Receiv
0eb0: 65 64 20 3c 3c 20 27 5c 22 27 20 3c 3c 20 65 6e ed << '\"' << en
0ec0: 64 6c 3b 20 7d 20 7d 0d 0a 23 64 65 66 69 6e 65 dl; } }..#define
0ed0: 20 43 41 53 45 28 4e 29 20 7b 63 65 72 72 20 3c CASE(N) {cerr <
0ee0: 3c 20 22 54 65 73 74 20 43 61 73 65 20 23 22 20 < "Test Case #"
0ef0: 3c 3c 20 4e 20 3c 3c 20 22 2e 2e 2e 22 20 3c 3c << N << "..." <<
0f00: 20 66 6c 75 73 68 3b 20 73 74 61 72 74 5f 74 69 flush; start_ti
0f10: 6d 65 3d 63 6c 6f 63 6b 28 29 3b 0d 0a 23 64 65 me=clock();..#de
0f20: 66 69 6e 65 20 45 4e 44 09 20 76 65 72 69 66 79 fine END. verify
0f30: 5f 63 61 73 65 28 5f 2c 20 42 61 74 6d 61 6e 41 _case(_, BatmanA
0f40: 6e 64 52 6f 62 69 6e 28 29 2e 6d 69 6e 41 72 65 ndRobin().minAre
0f50: 61 28 78 2c 20 79 29 29 3b 7d 0d 0a 69 6e 74 20 a(x, y));}..int
0f60: 6d 61 69 6e 28 29 7b 0d 0a 0d 0a 43 41 53 45 28 main(){....CASE(
0f70: 30 29 0d 0a 09 69 6e 74 20 78 5f 5b 5d 20 3d 20 0)...int x_[] =
0f80: 7b 31 30 30 2c 31 30 30 2c 39 30 2c 39 30 2c 2d {100,100,90,90,-
0f90: 31 30 30 2c 2d 31 30 30 2c 2d 39 30 2c 2d 39 30 100,-100,-90,-90
0fa0: 7d 3b 0d 0a 09 20 20 76 65 63 74 6f 72 20 3c 69 };... vector <i
0fb0: 6e 74 3e 20 78 28 78 5f 2c 20 78 5f 2b 73 69 7a nt> x(x_, x_+siz
0fc0: 65 6f 66 28 78 5f 29 2f 73 69 7a 65 6f 66 28 2a eof(x_)/sizeof(*
0fd0: 78 5f 29 29 3b 20 0d 0a 09 69 6e 74 20 79 5f 5b x_)); ...int y_[
0fe0: 5d 20 3d 20 7b 31 30 30 2c 39 30 2c 31 30 30 2c ] = {100,90,100,
0ff0: 39 30 2c 2d 31 30 30 2c 2d 39 30 2c 2d 31 30 30 90,-100,-90,-100
1000: 2c 2d 39 30 7d 3b 0d 0a 09 20 20 76 65 63 74 6f ,-90};... vecto
1010: 72 20 3c 69 6e 74 3e 20 79 28 79 5f 2c 20 79 5f r <int> y(y_, y_
1020: 2b 73 69 7a 65 6f 66 28 79 5f 29 2f 73 69 7a 65 +sizeof(y_)/size
1030: 6f 66 28 2a 79 5f 29 29 3b 20 0d 0a 09 64 6f 75 of(*y_)); ...dou
1040: 62 6c 65 20 5f 20 3d 20 31 30 30 2e 30 3b 20 0d ble _ = 100.0; .
1050: 0a 45 4e 44 0d 0a 43 41 53 45 28 31 29 0d 0a 09 .END..CASE(1)...
1060: 69 6e 74 20 78 5f 5b 5d 20 3d 20 7b 2d 31 30 30 int x_[] = {-100
1070: 30 2c 2d 31 30 30 30 2c 31 30 30 30 2c 31 30 30 0,-1000,1000,100
1080: 30 2c 31 30 30 30 2c 2d 31 30 30 30 7d 3b 0d 0a 0,1000,-1000};..
1090: 09 20 20 76 65 63 74 6f 72 20 3c 69 6e 74 3e 20 . vector <int>
10a0: 78 28 78 5f 2c 20 78 5f 2b 73 69 7a 65 6f 66 28 x(x_, x_+sizeof(
10b0: 78 5f 29 2f 73 69 7a 65 6f 66 28 2a 78 5f 29 29 x_)/sizeof(*x_))
10c0: 3b 20 0d 0a 09 69 6e 74 20 79 5f 5b 5d 20 3d 20 ; ...int y_[] =
10d0: 7b 2d 31 30 30 30 2c 31 30 30 30 2c 2d 31 30 30 {-1000,1000,-100
10e0: 30 2c 31 30 30 30 2c 30 2c 30 7d 3b 0d 0a 09 20 0,1000,0,0};...
10f0: 20 76 65 63 74 6f 72 20 3c 69 6e 74 3e 20 79 28 vector <int> y(
1100: 79 5f 2c 20 79 5f 2b 73 69 7a 65 6f 66 28 79 5f y_, y_+sizeof(y_
1110: 29 2f 73 69 7a 65 6f 66 28 2a 79 5f 29 29 3b 20 )/sizeof(*y_));
1120: 0d 0a 09 64 6f 75 62 6c 65 20 5f 20 3d 20 30 2e ...double _ = 0.
1130: 30 3b 20 0d 0a 45 4e 44 0d 0a 43 41 53 45 28 32 0; ..END..CASE(2
1140: 29 0d 0a 09 69 6e 74 20 78 5f 5b 5d 20 3d 20 7b )...int x_[] = {
1150: 2d 31 30 30 30 2c 2d 31 30 30 30 2c 31 30 30 30 -1000,-1000,1000
1160: 2c 31 30 30 30 2c 30 7d 3b 0d 0a 09 20 20 76 65 ,1000,0};... ve
1170: 63 74 6f 72 20 3c 69 6e 74 3e 20 78 28 78 5f 2c ctor <int> x(x_,
1180: 20 78 5f 2b 73 69 7a 65 6f 66 28 78 5f 29 2f 73 x_+sizeof(x_)/s
1190: 69 7a 65 6f 66 28 2a 78 5f 29 29 3b 20 0d 0a 09 izeof(*x_)); ...
11a0: 69 6e 74 20 79 5f 5b 5d 20 3d 20 7b 2d 31 30 30 int y_[] = {-100
11b0: 30 2c 31 30 30 30 2c 2d 31 30 30 30 2c 31 30 30 0,1000,-1000,100
11c0: 30 2c 30 7d 3b 0d 0a 09 20 20 76 65 63 74 6f 72 0,0};... vector
11d0: 20 3c 69 6e 74 3e 20 79 28 79 5f 2c 20 79 5f 2b <int> y(y_, y_+
11e0: 73 69 7a 65 6f 66 28 79 5f 29 2f 73 69 7a 65 6f sizeof(y_)/sizeo
11f0: 66 28 2a 79 5f 29 29 3b 20 0d 0a 09 64 6f 75 62 f(*y_)); ...doub
1200: 6c 65 20 5f 20 3d 20 31 30 30 30 30 30 30 2e 30 le _ = 1000000.0
1210: 3b 20 0d 0a 45 4e 44 0d 0a 43 41 53 45 28 33 29 ; ..END..CASE(3)
1220: 0d 0a 09 69 6e 74 20 78 5f 5b 5d 20 3d 20 7b 2d ...int x_[] = {-
1230: 39 30 34 2c 2d 38 31 32 2c 2d 37 36 33 2c 2d 37 904,-812,-763,-7
1240: 33 35 2c 2d 36 39 32 2c 2d 36 31 34 2c 2d 36 30 35,-692,-614,-60
1250: 32 2c 2d 35 36 33 2c 2d 34 33 35 2c 2d 32 34 33 2,-563,-435,-243
1260: 2c 2d 38 37 2c 2d 35 32 2c 2d 32 38 2c 31 32 31 ,-87,-52,-28,121
1270: 2c 31 32 36 2c 31 34 39 2c 31 35 37 2c 31 38 35 ,126,149,157,185
1280: 2c 33 31 35 2c 33 33 36 2c 33 39 30 2c 34 37 30 ,315,336,390,470
1290: 2c 35 32 38 2c 35 39 31 2c 36 37 33 2c 37 39 38 ,528,591,673,798
12a0: 2c 38 31 35 2c 38 33 37 2c 38 35 33 2c 38 37 34 ,815,837,853,874
12b0: 7d 3b 0d 0a 09 20 20 76 65 63 74 6f 72 20 3c 69 };... vector <i
12c0: 6e 74 3e 20 78 28 78 5f 2c 20 78 5f 2b 73 69 7a nt> x(x_, x_+siz
12d0: 65 6f 66 28 78 5f 29 2f 73 69 7a 65 6f 66 28 2a eof(x_)/sizeof(*
12e0: 78 5f 29 29 3b 20 0d 0a 09 69 6e 74 20 79 5f 5b x_)); ...int y_[
12f0: 5d 20 3d 20 7b 37 38 36 2c 31 30 2c 2d 31 34 34 ] = {786,10,-144
1300: 2c 39 34 39 2c 33 37 2c 2d 38 35 37 2c 2d 34 34 ,949,37,-857,-44
1310: 36 2c 2d 39 36 39 2c 2d 38 36 31 2c 2d 37 31 32 6,-969,-861,-712
1320: 2c 35 2c 2d 39 37 32 2c 2d 33 2c 2d 32 30 32 2c ,5,-972,-3,-202,
1330: 2d 38 34 35 2c 35 35 39 2c 2d 32 34 34 2c 2d 35 -845,559,-244,-5
1340: 34 32 2c 2d 34 32 31 2c 34 32 32 2c 35 32 36 2c 42,-421,422,526,
1350: 2d 35 30 31 2c 2d 37 39 31 2c 2d 38 39 39 2c 2d -501,-791,-899,-
1360: 33 31 35 2c 32 38 31 2c 2d 32 37 35 2c 34 36 37 315,281,-275,467
1370: 2c 37 34 33 2c 2d 33 32 31 7d 3b 0d 0a 09 20 20 ,743,-321};...
1380: 76 65 63 74 6f 72 20 3c 69 6e 74 3e 20 79 28 79 vector <int> y(y
1390: 5f 2c 20 79 5f 2b 73 69 7a 65 6f 66 28 79 5f 29 _, y_+sizeof(y_)
13a0: 2f 73 69 7a 65 6f 66 28 2a 79 5f 29 29 3b 20 0d /sizeof(*y_)); .
13b0: 0a 09 64 6f 75 62 6c 65 20 5f 20 3d 20 31 30 36 ..double _ = 106
13c0: 37 34 37 32 2e 30 3b 20 0d 0a 45 4e 44 0d 0a 43 7472.0; ..END..C
13d0: 41 53 45 28 34 29 0d 0a 09 69 6e 74 20 78 5f 5b ASE(4)...int x_[
13e0: 5d 20 3d 20 7b 2d 39 30 34 2c 2d 38 31 32 2c 2d ] = {-904,-812,-
13f0: 37 36 33 2c 2d 37 33 35 2c 2d 36 39 32 2c 2d 36 763,-735,-692,-6
1400: 31 34 2c 2d 36 30 32 2c 2d 35 36 33 2c 2d 34 33 14,-602,-563,-43
1410: 35 2c 2d 32 34 33 2c 2d 38 37 2c 2d 35 32 2c 2d 5,-243,-87,-52,-
1420: 32 38 2c 31 32 31 2c 31 32 36 2c 31 34 39 2c 31 28,121,126,149,1
1430: 35 37 2c 31 38 35 2c 33 31 35 2c 33 33 36 2c 33 57,185,315,336,3
1440: 39 30 2c 34 37 30 2c 35 32 38 2c 35 39 31 2c 36 90,470,528,591,6
1450: 37 33 2c 37 39 38 2c 38 31 35 2c 38 33 37 2c 38 73,798,815,837,8
1460: 35 33 2c 38 37 34 2c 31 2c 32 2c 33 2c 34 2c 35 53,874,1,2,3,4,5
1470: 2c 36 2c 37 2c 38 2c 39 2c 31 30 2c 31 31 2c 31 ,6,7,8,9,10,11,1
1480: 32 2c 31 33 2c 31 34 2c 31 35 2c 31 36 2c 31 37 2,13,14,15,16,17
1490: 2c 31 38 2c 31 39 2c 32 30 7d 3b 0d 0a 09 20 20 ,18,19,20};...
14a0: 76 65 63 74 6f 72 20 3c 69 6e 74 3e 20 78 28 78 vector <int> x(x
14b0: 5f 2c 20 78 5f 2b 73 69 7a 65 6f 66 28 78 5f 29 _, x_+sizeof(x_)
14c0: 2f 73 69 7a 65 6f 66 28 2a 78 5f 29 29 3b 20 0d /sizeof(*x_)); .
14d0: 0a 09 69 6e 74 20 79 5f 5b 5d 20 3d 20 7b 37 38 ..int y_[] = {78
14e0: 36 2c 31 30 2c 2d 31 34 34 2c 39 34 39 2c 33 37 6,10,-144,949,37
14f0: 2c 2d 38 35 37 2c 2d 34 34 36 2c 2d 39 36 39 2c ,-857,-446,-969,
1500: 2d 38 36 31 2c 2d 37 31 32 2c 35 2c 2d 39 37 32 -861,-712,5,-972
1510: 2c 2d 33 2c 2d 32 30 32 2c 2d 38 34 35 2c 35 35 ,-3,-202,-845,55
1520: 39 2c 2d 32 34 34 2c 2d 35 34 32 2c 2d 34 32 31 9,-244,-542,-421
1530: 2c 34 32 32 2c 35 32 36 2c 2d 35 30 31 2c 2d 37 ,422,526,-501,-7
1540: 39 31 2c 2d 38 39 39 2c 2d 33 31 35 2c 32 38 31 91,-899,-315,281
1550: 2c 2d 32 37 35 2c 34 36 37 2c 37 34 33 2c 2d 33 ,-275,467,743,-3
1560: 32 31 2c 31 2c 32 2c 33 2c 34 2c 35 2c 36 2c 37 21,1,2,3,4,5,6,7
1570: 2c 38 2c 39 2c 31 30 2c 31 31 2c 31 32 2c 31 33 ,8,9,10,11,12,13
1580: 2c 31 34 2c 31 35 2c 31 36 2c 31 37 2c 31 38 2c ,14,15,16,17,18,
1590: 31 39 2c 32 30 7d 3b 0d 0a 09 20 20 76 65 63 74 19,20};... vect
15a0: 6f 72 20 3c 69 6e 74 3e 20 79 28 79 5f 2c 20 79 or <int> y(y_, y
15b0: 5f 2b 73 69 7a 65 6f 66 28 79 5f 29 2f 73 69 7a _+sizeof(y_)/siz
15c0: 65 6f 66 28 2a 79 5f 29 29 3b 20 0d 0a 09 64 6f eof(*y_)); ...do
15d0: 75 62 6c 65 20 5f 20 3d 20 2d 31 3b 20 0d 0a 45 uble _ = -1; ..E
15e0: 4e 44 0d 0a 2f 2a 0d 0a 43 41 53 45 28 35 29 0d ND../*..CASE(5).
15f0: 0a 09 69 6e 74 20 78 5f 5b 5d 20 3d 20 3b 0d 0a ..int x_[] = ;..
1600: 09 20 20 76 65 63 74 6f 72 20 3c 69 6e 74 3e 20 . vector <int>
1610: 78 28 78 5f 2c 20 78 5f 2b 73 69 7a 65 6f 66 28 x(x_, x_+sizeof(
1620: 78 5f 29 2f 73 69 7a 65 6f 66 28 2a 78 5f 29 29 x_)/sizeof(*x_))
1630: 3b 20 0d 0a 09 69 6e 74 20 79 5f 5b 5d 20 3d 20 ; ...int y_[] =
1640: 3b 0d 0a 09 20 20 76 65 63 74 6f 72 20 3c 69 6e ;... vector <in
1650: 74 3e 20 79 28 79 5f 2c 20 79 5f 2b 73 69 7a 65 t> y(y_, y_+size
1660: 6f 66 28 79 5f 29 2f 73 69 7a 65 6f 66 28 2a 79 of(y_)/sizeof(*y
1670: 5f 29 29 3b 20 0d 0a 09 64 6f 75 62 6c 65 20 5f _)); ...double _
1680: 20 3d 20 3b 20 0d 0a 45 4e 44 0d 0a 2a 2f 0d 0a = ; ..END..*/..
1690: 7d 0d 0a 2f 2f 20 45 4e 44 20 43 55 54 20 48 45 }..// END CUT HE
16a0: 52 45 0d 0a RE..