Artifact f28d7402b7cb45295c7d9e9e95e0544528580e75:
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 54 68 65 20 63 69 72 63 6c 65 20 70 .// The circle p
0050: 61 73 73 69 6e 67 20 74 68 72 65 65 20 70 6f 69 assing three poi
0060: 6e 74 73 0a 2f 2f 0a 2f 2f 20 56 65 72 69 66 69 nts.//.// Verifi
0070: 65 64 20 62 79 0a 2f 2f 20 20 20 2d 20 41 4f 4a ed by.// - AOJ
0080: 20 30 30 31 32 20 28 6f 6e 6c 79 20 74 72 69 61 0012 (only tria
0090: 6e 67 6c 65 73 29 0a 2f 2f 2d 2d 2d 2d 2d 2d 2d ngles).//-------
00a0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
00b0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
00c0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
00d0: 2d 2d 2d 2d 2d 2d 0a 0a 64 6f 75 62 6c 65 20 6f ------..double o
00e0: 75 74 65 72 5f 70 72 6f 64 28 63 6f 6e 73 74 20 uter_prod(const
00f0: 43 4d 50 26 20 61 2c 20 63 6f 6e 73 74 20 43 4d CMP& a, const CM
0100: 50 26 20 62 29 20 7b 20 72 65 74 75 72 6e 20 69 P& b) { return i
0110: 6d 61 67 28 63 6f 6e 6a 28 61 29 2a 62 29 3b 20 mag(conj(a)*b);
0120: 7d 0a 0a 62 6f 6f 6c 20 70 6f 69 6e 74 5f 69 6e }..bool point_in
0130: 5f 70 6f 6c 79 67 6f 6e 28 20 76 65 63 74 6f 72 _polygon( vector
0140: 3c 43 4d 50 3e 26 20 70 73 2c 20 43 4d 50 20 70 <CMP>& ps, CMP p
0150: 20 29 0a 7b 0a 09 62 6f 6f 6c 20 69 6e 20 3d 20 ).{..bool in =
0160: 66 61 6c 73 65 3b 0a 09 66 6f 72 28 69 6e 74 20 false;..for(int
0170: 69 3d 30 3b 20 69 3c 70 73 2e 73 69 7a 65 28 29 i=0; i<ps.size()
0180: 3b 20 2b 2b 69 29 20 7b 0a 09 09 43 4d 50 20 61 ; ++i) {...CMP a
0190: 20 3d 20 70 73 5b 69 5d 20 2d 20 70 3b 0a 09 09 = ps[i] - p;...
01a0: 43 4d 50 20 62 20 3d 20 70 73 5b 28 69 2b 31 29 CMP b = ps[(i+1)
01b0: 25 70 73 2e 73 69 7a 65 28 29 5d 20 2d 20 70 3b %ps.size()] - p;
01c0: 0a 09 09 69 66 28 61 2e 69 6d 61 67 28 29 20 3e ...if(a.imag() >
01d0: 20 62 2e 69 6d 61 67 28 29 29 20 73 77 61 70 28 b.imag()) swap(
01e0: 61 2c 62 29 3b 0a 09 09 69 66 28 61 2e 69 6d 61 a,b);...if(a.ima
01f0: 67 28 29 3c 3d 30 20 26 26 20 30 3c 62 2e 69 6d g()<=0 && 0<b.im
0200: 61 67 28 29 29 20 7b 0a 09 09 09 69 66 28 20 6f ag()) {....if( o
0210: 75 74 65 72 5f 70 72 6f 64 28 61 2c 62 29 20 3c uter_prod(a,b) <
0220: 20 30 20 29 0a 09 09 09 09 69 6e 20 3d 20 21 69 0 ).....in = !i
0230: 6e 3b 0a 09 09 7d 0a 09 09 2f 2f 69 66 28 20 6f n;...}...//if( o
0240: 75 74 65 72 5f 70 72 6f 64 28 61 2c 62 29 3d 3d uter_prod(a,b)==
0250: 30 20 26 26 20 69 6e 6e 65 72 5f 70 72 6f 64 28 0 && inner_prod(
0260: 61 2c 62 29 3c 3d 30 20 29 20 72 65 74 75 72 6e a,b)<=0 ) return
0270: 20 4f 4e 3b 0a 09 7d 0a 09 72 65 74 75 72 6e 20 ON;..}..return
0280: 69 6e 3b 0a 7d 0a in;.}.