Artifact 9ffbc36d1d4aa6a7da03e785207383c67286dbcf:
0000: 0a 2f 2f 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d .//-------------
0010: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0020: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0030: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0040: 0a 2f 2f 20 43 6f 6e 76 65 78 20 48 75 6c 6c 20 .// Convex Hull
0050: 2d 2d 20 47 69 66 74 20 57 72 61 70 70 69 6e 67 -- Gift Wrapping
0060: 0a 2f 2f 20 20 20 4f 28 4e 20 6c 6f 67 20 4e 29 .// O(N log N)
0070: 0a 2f 2f 0a 2f 2f 20 54 6f 44 6f 20 3a 20 52 65 .//.// ToDo : Re
0080: 77 72 69 74 65 20 62 79 20 43 43 57 2e 2e 2e 0a write by CCW....
0090: 2f 2f 0a 2f 2f 20 56 65 72 69 66 69 65 64 20 62 //.// Verified b
00a0: 79 0a 2f 2f 20 20 20 2d 20 53 52 4d 20 33 33 36 y.// - SRM 336
00b0: 20 44 69 76 31 20 4c 56 33 0a 2f 2f 2d 2d 2d 2d Div1 LV3.//----
00c0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
00d0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
00e0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
00f0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 0a 0a 62 6f 6f 6c 20 ---------..bool
0100: 62 79 59 28 20 43 4d 50 20 61 2c 20 43 4d 50 20 byY( CMP a, CMP
0110: 62 20 29 0a 7b 0a 09 69 66 28 20 61 2e 69 6d 61 b ).{..if( a.ima
0120: 67 28 29 20 3d 3d 20 62 2e 69 6d 61 67 28 29 20 g() == b.imag()
0130: 29 0a 09 09 72 65 74 75 72 6e 20 61 2e 72 65 61 )...return a.rea
0140: 6c 28 29 20 3c 20 62 2e 72 65 61 6c 28 29 3b 0a l() < b.real();.
0150: 09 72 65 74 75 72 6e 20 61 2e 69 6d 61 67 28 29 .return a.imag()
0160: 20 3c 20 62 2e 69 6d 61 67 28 29 3b 0a 7d 0a 0a < b.imag();.}..
0170: 62 6f 6f 6c 20 62 79 41 72 67 28 20 43 4d 50 20 bool byArg( CMP
0180: 61 2c 20 43 4d 50 20 62 20 29 0a 7b 0a 09 72 65 a, CMP b ).{..re
0190: 74 75 72 6e 20 61 72 67 28 61 29 20 3c 20 61 72 turn arg(a) < ar
01a0: 67 28 62 29 3b 0a 7d 0a 0a 62 6f 6f 6c 20 69 73 g(b);.}..bool is
01b0: 52 69 67 68 74 28 20 43 4d 50 20 61 2c 20 43 4d Right( CMP a, CM
01c0: 50 20 62 2c 20 43 4d 50 20 63 20 29 0a 7b 0a 09 P b, CMP c ).{..
01d0: 72 65 74 75 72 6e 20 61 72 67 28 28 63 2d 62 29 return arg((c-b)
01e0: 20 2f 20 28 62 2d 61 29 29 20 3c 20 30 3b 0a 7d / (b-a)) < 0;.}
01f0: 0a 0a 76 65 63 74 6f 72 3c 43 4d 50 3e 20 63 6f ..vector<CMP> co
0200: 6e 76 65 78 5f 68 75 6c 6c 28 20 76 65 63 74 6f nvex_hull( vecto
0210: 72 3c 43 4d 50 3e 20 70 20 29 0a 7b 0a 09 76 65 r<CMP> p ).{..ve
0220: 63 74 6f 72 3c 43 4d 50 3e 3a 3a 69 74 65 72 61 ctor<CMP>::itera
0230: 74 6f 72 20 69 74 20 3d 20 6d 69 6e 5f 65 6c 65 tor it = min_ele
0240: 6d 65 6e 74 28 20 70 2e 62 65 67 69 6e 28 29 2c ment( p.begin(),
0250: 20 70 2e 65 6e 64 28 29 2c 20 62 79 59 20 29 3b p.end(), byY );
0260: 0a 09 43 4d 50 20 6f 20 3d 20 2a 69 74 3b 0a 09 ..CMP o = *it;..
0270: 70 2e 65 72 61 73 65 28 69 74 29 3b 0a 09 66 6f p.erase(it);..fo
0280: 72 28 69 6e 74 20 69 3d 30 3b 20 69 3c 70 2e 73 r(int i=0; i<p.s
0290: 69 7a 65 28 29 3b 20 2b 2b 69 29 0a 09 09 70 5b ize(); ++i)...p[
02a0: 69 5d 20 2d 3d 20 6f 3b 0a 09 73 6f 72 74 28 20 i] -= o;..sort(
02b0: 70 2e 62 65 67 69 6e 28 29 2c 20 70 2e 65 6e 64 p.begin(), p.end
02c0: 28 29 2c 20 62 79 41 72 67 20 29 3b 0a 0a 09 76 (), byArg );...v
02d0: 65 63 74 6f 72 3c 43 4d 50 3e 20 71 3b 0a 09 71 ector<CMP> q;..q
02e0: 2e 70 75 73 68 5f 62 61 63 6b 28 20 43 4d 50 28 .push_back( CMP(
02f0: 30 2c 30 29 20 29 3b 0a 09 71 2e 70 75 73 68 5f 0,0) );..q.push_
0300: 62 61 63 6b 28 20 70 5b 30 5d 20 29 3b 0a 09 66 back( p[0] );..f
0310: 6f 72 28 69 6e 74 20 69 3d 31 3b 20 69 3c 70 2e or(int i=1; i<p.
0320: 73 69 7a 65 28 29 3b 20 2b 2b 69 29 20 7b 0a 09 size(); ++i) {..
0330: 09 77 68 69 6c 65 28 20 69 73 52 69 67 68 74 28 .while( isRight(
0340: 71 5b 71 2e 73 69 7a 65 28 29 2d 32 5d 2c 20 71 q[q.size()-2], q
0350: 5b 71 2e 73 69 7a 65 28 29 2d 31 5d 2c 20 70 5b [q.size()-1], p[
0360: 69 5d 29 20 29 0a 09 09 09 71 2e 70 6f 70 5f 62 i]) )....q.pop_b
0370: 61 63 6b 28 29 3b 0a 09 09 71 2e 70 75 73 68 5f ack();...q.push_
0380: 62 61 63 6b 28 20 70 5b 69 5d 20 29 3b 0a 09 7d back( p[i] );..}
0390: 0a 09 66 6f 72 28 69 6e 74 20 69 3d 30 3b 20 69 ..for(int i=0; i
03a0: 3c 71 2e 73 69 7a 65 28 29 3b 20 2b 2b 69 29 0a <q.size(); ++i).
03b0: 09 09 71 5b 69 5d 20 2b 3d 20 6f 3b 0a 09 72 65 ..q[i] += o;..re
03c0: 74 75 72 6e 20 71 3b 0a 7d 0a turn q;.}.