Artifact 05f672d15009c4b53de46381ddfeb3a685fba3df:
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 20 43 4d 50 20 61 uter_prod( CMP a
00f0: 2c 20 43 4d 50 20 62 20 29 0a 7b 0a 09 72 65 74 , CMP b ).{..ret
0100: 75 72 6e 20 28 61 2e 72 65 61 6c 28 29 2a 62 2e urn (a.real()*b.
0110: 69 6d 61 67 28 29 20 2d 20 62 2e 72 65 61 6c 28 imag() - b.real(
0120: 29 2a 61 2e 69 6d 61 67 28 29 29 2f 32 3b 0a 7d )*a.imag())/2;.}
0130: 0a 0a 62 6f 6f 6c 20 70 6f 69 6e 74 5f 69 6e 5f ..bool point_in_
0140: 70 6f 6c 79 67 6f 6e 28 20 76 65 63 74 6f 72 3c polygon( vector<
0150: 43 4d 50 3e 26 20 70 73 2c 20 43 4d 50 20 70 20 CMP>& ps, CMP p
0160: 29 0a 7b 0a 09 62 6f 6f 6c 20 69 6e 20 3d 20 66 ).{..bool in = f
0170: 61 6c 73 65 3b 0a 09 66 6f 72 28 69 6e 74 20 69 alse;..for(int i
0180: 3d 30 3b 20 69 3c 70 73 2e 73 69 7a 65 28 29 3b =0; i<ps.size();
0190: 20 2b 2b 69 29 20 7b 0a 09 09 43 4d 50 20 61 20 ++i) {...CMP a
01a0: 3d 20 70 73 5b 69 5d 20 2d 20 70 3b 0a 09 09 43 = ps[i] - p;...C
01b0: 4d 50 20 62 20 3d 20 70 73 5b 28 69 2b 31 29 25 MP b = ps[(i+1)%
01c0: 70 73 2e 73 69 7a 65 28 29 5d 20 2d 20 70 3b 0a ps.size()] - p;.
01d0: 09 09 69 66 28 61 2e 69 6d 61 67 28 29 20 3e 20 ..if(a.imag() >
01e0: 62 2e 69 6d 61 67 28 29 29 20 73 77 61 70 28 61 b.imag()) swap(a
01f0: 2c 62 29 3b 0a 09 09 69 66 28 61 2e 69 6d 61 67 ,b);...if(a.imag
0200: 28 29 3c 3d 30 20 26 26 20 30 3c 62 2e 69 6d 61 ()<=0 && 0<b.ima
0210: 67 28 29 29 20 7b 0a 09 09 09 69 66 28 20 6f 75 g()) {....if( ou
0220: 74 65 72 5f 70 72 6f 64 28 61 2c 62 29 20 3c 20 ter_prod(a,b) <
0230: 30 20 29 0a 09 09 09 09 69 6e 20 3d 20 21 69 6e 0 ).....in = !in
0240: 3b 0a 09 09 7d 0a 09 09 2f 2f 69 66 28 20 6f 75 ;...}...//if( ou
0250: 74 65 72 5f 70 72 6f 64 28 61 2c 62 29 3d 3d 30 ter_prod(a,b)==0
0260: 20 26 26 20 69 6e 6e 65 72 5f 70 72 6f 64 28 61 && inner_prod(a
0270: 2c 62 29 3c 3d 30 20 29 20 72 65 74 75 72 6e 20 ,b)<=0 ) return
0280: 4f 4e 3b 0a 09 7d 0a 09 72 65 74 75 72 6e 20 69 ON;..}..return i
0290: 6e 3b 0a 7d 0a n;.}.