Artifact 40885cae01887a2cac5f874f130e221317294827:
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 30 0a 2f 2f 2d 2d 2d 2d 2d 2d 2d 2d 0010.//--------
0090: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
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 0a 0a 76 65 63 74 6f 72 3c 64 6f -----..vector<do
00d0: 75 62 6c 65 3e 20 73 6f 6c 76 65 5f 6c 69 6e 65 uble> solve_line
00e0: 61 72 5f 65 71 28 20 69 6e 74 20 6e 2c 20 76 65 ar_eq( int n, ve
00f0: 63 74 6f 72 3c 20 76 65 63 74 6f 72 3c 64 6f 75 ctor< vector<dou
0100: 62 6c 65 3e 20 3e 20 4d 2c 20 63 6f 6e 73 74 20 ble> > M, const
0110: 76 65 63 74 6f 72 3c 64 6f 75 62 6c 65 3e 26 20 vector<double>&
0120: 56 20 29 0a 7b 0a 09 76 65 63 74 6f 72 3c 64 6f V ).{..vector<do
0130: 75 62 6c 65 3e 20 41 28 56 29 3b 0a 09 66 6f 72 uble> A(V);..for
0140: 28 69 6e 74 20 69 3d 30 3b 20 69 3c 6e 3b 20 2b (int i=0; i<n; +
0150: 2b 69 29 0a 09 7b 0a 09 09 2f 2f 20 70 69 76 6f +i)..{...// pivo
0160: 74 0a 09 09 69 66 28 20 4d 5b 69 5d 5b 69 5d 20 t...if( M[i][i]
0170: 3d 3d 20 30 20 29 0a 09 09 09 66 6f 72 28 69 6e == 0 )....for(in
0180: 74 20 6a 3d 69 2b 31 3b 20 6a 3c 6e 3b 20 2b 2b t j=i+1; j<n; ++
0190: 6a 29 0a 09 09 09 09 69 66 28 20 4d 5b 6a 5d 5b j).....if( M[j][
01a0: 69 5d 20 21 3d 20 30 20 29 0a 09 09 09 09 09 7b i] != 0 )......{
01b0: 73 77 61 70 28 4d 5b 69 5d 2c 20 4d 5b 6a 5d 29 swap(M[i], M[j])
01c0: 3b 20 73 77 61 70 28 41 5b 69 5d 2c 20 41 5b 6a ; swap(A[i], A[j
01d0: 5d 29 3b 20 62 72 65 61 6b 3b 7d 0a 09 09 69 66 ]); break;}...if
01e0: 28 20 4d 5b 69 5d 5b 69 5d 20 3d 3d 20 30 20 29 ( M[i][i] == 0 )
01f0: 0a 09 09 09 74 68 72 6f 77 20 22 6e 6f 20 61 6e ....throw "no an
0200: 73 65 72 22 3b 0a 0a 09 09 2f 2f 20 4d 5b 69 5d ser";....// M[i]
0210: 5b 69 5d 20 3c 2d 2d 20 31 0a 09 09 64 6f 75 62 [i] <-- 1...doub
0220: 6c 65 20 70 20 3d 20 4d 5b 69 5d 5b 69 5d 3b 0a le p = M[i][i];.
0230: 09 09 66 6f 72 28 69 6e 74 20 6a 3d 69 3b 20 6a ..for(int j=i; j
0240: 3c 6e 3b 20 2b 2b 6a 29 0a 09 09 09 4d 5b 69 5d <n; ++j)....M[i]
0250: 5b 6a 5d 20 2f 3d 20 70 3b 0a 09 09 41 5b 69 5d [j] /= p;...A[i]
0260: 20 2f 3d 20 70 3b 0a 0a 09 09 2f 2f 20 4d 5b 2a /= p;....// M[*
0270: 5d 5b 69 5d 20 3c 2d 2d 20 30 0a 09 09 66 6f 72 ][i] <-- 0...for
0280: 28 69 6e 74 20 6a 3d 30 3b 20 6a 3c 6e 3b 20 2b (int j=0; j<n; +
0290: 2b 6a 29 20 69 66 28 6a 21 3d 69 29 0a 09 09 7b +j) if(j!=i)...{
02a0: 0a 09 09 09 64 6f 75 62 6c 65 20 72 20 3d 20 4d ....double r = M
02b0: 5b 6a 5d 5b 69 5d 3b 0a 09 09 09 66 6f 72 28 69 [j][i];....for(i
02c0: 6e 74 20 6b 3d 69 3b 20 6b 3c 6e 3b 20 2b 2b 6b nt k=i; k<n; ++k
02d0: 29 0a 09 09 09 09 4d 5b 6a 5d 5b 6b 5d 20 2d 3d ).....M[j][k] -=
02e0: 20 4d 5b 69 5d 5b 6b 5d 20 2a 20 72 3b 0a 09 09 M[i][k] * r;...
02f0: 09 41 5b 6a 5d 20 2d 3d 20 41 5b 69 5d 20 2a 20 .A[j] -= A[i] *
0300: 72 3b 0a 09 09 7d 0a 09 7d 0a 09 72 65 74 75 72 r;...}..}..retur
0310: 6e 20 41 3b 0a 7d 0a 0a 76 6f 69 64 20 63 69 72 n A;.}..void cir
0320: 63 6c 65 5f 33 70 74 28 20 43 4d 50 20 70 31 2c cle_3pt( CMP p1,
0330: 20 43 4d 50 20 70 32 2c 20 43 4d 50 20 70 33 2c CMP p2, CMP p3,
0340: 20 43 4d 50 2a 20 63 2c 20 64 6f 75 62 6c 65 2a CMP* c, double*
0350: 20 72 20 29 0a 7b 0a 09 70 32 20 2d 3d 20 70 31 r ).{..p2 -= p1
0360: 3b 0a 09 70 33 20 2d 3d 20 70 31 3b 0a 09 2f 2f ;..p3 -= p1;..//
0370: 20 63 20 3d 3d 20 70 32 2f 32 20 2b 20 41 20 70 c == p2/2 + A p
0380: 32 20 69 20 3d 3d 20 70 33 2f 32 20 2b 20 42 20 2 i == p3/2 + B
0390: 70 33 20 69 0a 0a 09 76 65 63 74 6f 72 3c 20 76 p3 i...vector< v
03a0: 65 63 74 6f 72 3c 64 6f 75 62 6c 65 3e 20 3e 20 ector<double> >
03b0: 4d 28 32 2c 20 76 65 63 74 6f 72 3c 64 6f 75 62 M(2, vector<doub
03c0: 6c 65 3e 28 32 29 29 3b 0a 09 76 65 63 74 6f 72 le>(2));..vector
03d0: 3c 64 6f 75 62 6c 65 3e 20 56 28 32 29 3b 0a 09 <double> V(2);..
03e0: 4d 5b 30 5d 5b 30 5d 20 3d 20 2d 70 32 2e 69 6d M[0][0] = -p2.im
03f0: 61 67 28 29 3b 20 4d 5b 30 5d 5b 31 5d 20 3d 20 ag(); M[0][1] =
0400: 2b 70 33 2e 69 6d 61 67 28 29 3b 20 56 5b 30 5d +p3.imag(); V[0]
0410: 20 3d 20 28 70 33 2e 72 65 61 6c 28 29 2d 70 32 = (p3.real()-p2
0420: 2e 72 65 61 6c 28 29 29 2f 32 2e 30 3b 0a 09 4d .real())/2.0;..M
0430: 5b 31 5d 5b 30 5d 20 3d 20 2b 70 32 2e 72 65 61 [1][0] = +p2.rea
0440: 6c 28 29 3b 20 4d 5b 31 5d 5b 31 5d 20 3d 20 2d l(); M[1][1] = -
0450: 70 33 2e 72 65 61 6c 28 29 3b 20 56 5b 31 5d 20 p3.real(); V[1]
0460: 3d 20 28 70 33 2e 69 6d 61 67 28 29 2d 70 32 2e = (p3.imag()-p2.
0470: 69 6d 61 67 28 29 29 2f 32 2e 30 3b 0a 09 56 20 imag())/2.0;..V
0480: 3d 20 73 6f 6c 76 65 5f 6c 69 6e 65 61 72 5f 65 = solve_linear_e
0490: 71 28 32 2c 20 4d 2c 20 56 29 3b 0a 0a 09 64 6f q(2, M, V);...do
04a0: 75 62 6c 65 20 41 3d 56 5b 30 5d 2c 20 42 3d 56 uble A=V[0], B=V
04b0: 5b 31 5d 3b 0a 09 2a 63 20 3d 20 70 31 20 2b 20 [1];..*c = p1 +
04c0: 70 32 2f 32 2e 30 20 2b 20 41 20 2a 20 70 32 20 p2/2.0 + A * p2
04d0: 2a 20 43 4d 50 28 30 2c 31 29 3b 0a 09 2a 72 20 * CMP(0,1);..*r
04e0: 3d 20 61 62 73 28 2a 63 20 2d 20 70 31 29 3b 0a = abs(*c - p1);.
04f0: 7d 0a }.