Artifact 75743e110118c49cd9a8cce9408438c0745cd246:
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 41 6e 64 72 65 77 27 73 20 4d 6f 6e 6f -- Andrew's Mono
0060: 74 6f 6e 65 20 43 68 61 69 6e 0a 2f 2f 20 20 20 tone Chain.//
0070: 4f 28 4e 20 6c 6f 67 20 4e 29 0a 2f 2f 0a 2f 2f O(N log N).//.//
0080: 20 56 65 72 69 66 69 65 64 20 62 79 0a 2f 2f 20 Verified by.//
0090: 20 20 2d 20 53 52 4d 20 33 33 36 20 44 69 76 31 - SRM 336 Div1
00a0: 20 4c 56 33 0a 2f 2f 20 20 20 2d 20 54 43 4f 30 LV3.// - TCO0
00b0: 39 20 52 6f 75 6e 64 32 20 4c 56 32 0a 2f 2f 20 9 Round2 LV2.//
00c0: 20 20 2d 20 53 52 4d 20 34 38 36 20 44 69 76 31 - SRM 486 Div1
00d0: 20 4c 56 33 0a 2f 2f 2d 2d 2d 2d 2d 2d 2d 2d 2d LV3.//---------
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 2d 2d 2d 2d 2d 2d 2d ----------------
0100: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0110: 2d 2d 2d 2d 0a 0a 64 6f 75 62 6c 65 20 6f 75 74 ----..double out
0120: 65 72 5f 70 72 6f 64 28 63 6f 6e 73 74 20 43 4d er_prod(const CM
0130: 50 26 20 61 2c 20 63 6f 6e 73 74 20 43 4d 50 26 P& a, const CMP&
0140: 20 62 29 20 7b 20 72 65 74 75 72 6e 20 69 6d 61 b) { return ima
0150: 67 28 63 6f 6e 6a 28 61 29 2a 62 29 3b 20 7d 0a g(conj(a)*b); }.
0160: 64 6f 75 62 6c 65 20 69 6e 6e 65 72 5f 70 72 6f double inner_pro
0170: 64 28 63 6f 6e 73 74 20 43 4d 50 26 20 61 2c 20 d(const CMP& a,
0180: 63 6f 6e 73 74 20 43 4d 50 26 20 62 29 20 7b 20 const CMP& b) {
0190: 72 65 74 75 72 6e 20 72 65 61 6c 28 63 6f 6e 6a return real(conj
01a0: 28 61 29 2a 62 29 3b 20 7d 0a 0a 69 6e 74 20 63 (a)*b); }..int c
01b0: 63 77 28 63 6f 6e 73 74 20 43 4d 50 26 20 61 2c cw(const CMP& a,
01c0: 20 43 4d 50 20 62 2c 20 43 4d 50 20 63 29 20 7b CMP b, CMP c) {
01d0: 0a 09 62 20 2d 3d 20 61 3b 20 63 20 2d 3d 20 61 ..b -= a; c -= a
01e0: 3b 0a 09 69 66 28 20 6f 75 74 65 72 5f 70 72 6f ;..if( outer_pro
01f0: 64 28 62 2c 63 29 20 3e 20 30 20 29 20 72 65 74 d(b,c) > 0 ) ret
0200: 75 72 6e 20 2b 31 3b 20 2f 2f 20 63 6f 75 6e 74 urn +1; // count
0210: 65 72 20 63 6c 6f 63 6b 77 69 73 65 0a 09 69 66 er clockwise..if
0220: 28 20 6f 75 74 65 72 5f 70 72 6f 64 28 62 2c 63 ( outer_prod(b,c
0230: 29 20 3c 20 30 20 29 20 72 65 74 75 72 6e 20 2d ) < 0 ) return -
0240: 31 3b 20 2f 2f 20 63 6c 6f 63 6b 77 69 73 65 0a 1; // clockwise.
0250: 09 69 66 28 20 69 6e 6e 65 72 5f 70 72 6f 64 28 .if( inner_prod(
0260: 62 2c 63 29 20 3c 20 30 20 29 20 72 65 74 75 72 b,c) < 0 ) retur
0270: 6e 20 2b 32 3b 20 2f 2f 20 63 2d 2d 61 2d 2d 62 n +2; // c--a--b
0280: 20 6f 6e 20 6c 69 6e 65 0a 09 69 66 28 20 6e 6f on line..if( no
0290: 72 6d 28 62 29 20 3c 20 6e 6f 72 6d 28 63 29 20 rm(b) < norm(c)
02a0: 29 20 20 20 72 65 74 75 72 6e 20 2d 32 3b 20 2f ) return -2; /
02b0: 2f 20 61 2d 2d 62 2d 2d 63 20 6f 6e 20 6c 69 6e / a--b--c on lin
02c0: 65 0a 09 72 65 74 75 72 6e 20 30 3b 0a 7d 0a 0a e..return 0;.}..
02d0: 62 6f 6f 6c 20 62 79 58 28 20 63 6f 6e 73 74 20 bool byX( const
02e0: 43 4d 50 26 20 61 2c 20 63 6f 6e 73 74 20 43 4d CMP& a, const CM
02f0: 50 26 20 62 20 29 20 7b 0a 09 69 66 28 20 61 2e P& b ) {..if( a.
0300: 72 65 61 6c 28 29 20 21 3d 20 62 2e 72 65 61 6c real() != b.real
0310: 28 29 20 29 0a 09 09 72 65 74 75 72 6e 20 61 2e () )...return a.
0320: 72 65 61 6c 28 29 20 3c 20 62 2e 72 65 61 6c 28 real() < b.real(
0330: 29 3b 0a 09 72 65 74 75 72 6e 20 61 2e 69 6d 61 );..return a.ima
0340: 67 28 29 20 3c 20 62 2e 69 6d 61 67 28 29 3b 0a g() < b.imag();.
0350: 7d 0a 0a 76 65 63 74 6f 72 3c 43 4d 50 3e 20 63 }..vector<CMP> c
0360: 6f 6e 76 65 78 5f 68 75 6c 6c 28 20 76 65 63 74 onvex_hull( vect
0370: 6f 72 3c 43 4d 50 3e 20 70 20 29 0a 7b 0a 09 23 or<CMP> p ).{..#
0380: 64 65 66 69 6e 65 20 49 53 5f 52 49 47 48 54 20 define IS_RIGHT
0390: 3c 30 20 20 20 2f 2f 20 73 6b 69 70 20 6f 6e 2d <0 // skip on-
03a0: 6c 69 6e 65 20 76 65 72 74 73 0a 09 2f 2f 23 64 line verts..//#d
03b0: 65 66 69 6e 65 20 49 53 5f 52 49 47 48 54 20 3d efine IS_RIGHT =
03c0: 3d 2d 31 20 2f 2f 20 74 61 6b 65 20 61 6c 6c 0a =-1 // take all.
03d0: 0a 09 73 6f 72 74 28 70 2e 62 65 67 69 6e 28 29 ..sort(p.begin()
03e0: 2c 20 70 2e 65 6e 64 28 29 2c 20 26 62 79 58 29 , p.end(), &byX)
03f0: 3b 0a 0a 09 76 65 63 74 6f 72 3c 43 4d 50 3e 20 ;...vector<CMP>
0400: 61 6e 73 3b 0a 09 66 6f 72 28 69 6e 74 20 69 3d ans;..for(int i=
0410: 30 3b 20 69 3c 70 2e 73 69 7a 65 28 29 3b 20 61 0; i<p.size(); a
0420: 6e 73 2e 70 75 73 68 5f 62 61 63 6b 28 70 5b 69 ns.push_back(p[i
0430: 2b 2b 5d 29 29 20 2f 2f 20 6c 65 66 74 2d 74 6f ++])) // left-to
0440: 2d 72 69 67 68 74 0a 09 09 77 68 69 6c 65 28 20 -right...while(
0450: 61 6e 73 2e 73 69 7a 65 28 29 3e 3d 32 20 26 26 ans.size()>=2 &&
0460: 20 63 63 77 28 61 6e 73 5b 61 6e 73 2e 73 69 7a ccw(ans[ans.siz
0470: 65 28 29 2d 32 5d 2c 20 61 6e 73 5b 61 6e 73 2e e()-2], ans[ans.
0480: 73 69 7a 65 28 29 2d 31 5d 2c 20 70 5b 69 5d 29 size()-1], p[i])
0490: 20 49 53 5f 52 49 47 48 54 20 29 0a 09 09 09 61 IS_RIGHT )....a
04a0: 6e 73 2e 70 6f 70 5f 62 61 63 6b 28 29 3b 0a 09 ns.pop_back();..
04b0: 69 66 28 20 61 6e 73 2e 73 69 7a 65 28 29 20 3d if( ans.size() =
04c0: 3d 20 70 2e 73 69 7a 65 28 29 20 29 0a 09 09 72 = p.size() )...r
04d0: 65 74 75 72 6e 20 61 6e 73 3b 0a 09 66 6f 72 28 eturn ans;..for(
04e0: 69 6e 74 20 69 3d 70 2e 73 69 7a 65 28 29 2d 32 int i=p.size()-2
04f0: 3b 20 69 3e 3d 30 3b 20 61 6e 73 2e 70 75 73 68 ; i>=0; ans.push
0500: 5f 62 61 63 6b 28 70 5b 69 2d 2d 5d 29 29 20 2f _back(p[i--])) /
0510: 2f 20 72 69 67 68 74 2d 74 6f 2d 6c 65 66 74 0a / right-to-left.
0520: 09 09 77 68 69 6c 65 28 20 61 6e 73 2e 73 69 7a ..while( ans.siz
0530: 65 28 29 3e 3d 32 20 26 26 20 63 63 77 28 61 6e e()>=2 && ccw(an
0540: 73 5b 61 6e 73 2e 73 69 7a 65 28 29 2d 32 5d 2c s[ans.size()-2],
0550: 20 61 6e 73 5b 61 6e 73 2e 73 69 7a 65 28 29 2d ans[ans.size()-
0560: 31 5d 2c 20 70 5b 69 5d 29 20 49 53 5f 52 49 47 1], p[i]) IS_RIG
0570: 48 54 20 29 0a 09 09 09 61 6e 73 2e 70 6f 70 5f HT )....ans.pop_
0580: 62 61 63 6b 28 29 3b 0a 09 61 6e 73 2e 70 6f 70 back();..ans.pop
0590: 5f 62 61 63 6b 28 29 3b 0a 09 72 65 74 75 72 6e _back();..return
05a0: 20 61 6e 73 3b 0a 7d 0a ans;.}.