Artifact f037935b3feedc1e1cb4051fc6c5d84565ec6355:
0000: 2f 2f 20 56 65 72 69 66 69 65 64 3a 20 70 61 72 // Verified: par
0010: 74 6c 79 20 62 79 20 67 65 6f 63 6f 6e 32 30 31 tly by geocon201
0020: 33 20 44 28 31 29 2e 0a 0a 2f 2f 20 43 72 6f 73 3 D(1)...// Cros
0030: 73 70 6f 69 6e 67 20 6f 66 20 61 20 6c 69 6e 65 spoing of a line
0040: 20 28 6e 6f 74 20 6c 69 6e 65 73 65 67 21 29 20 (not lineseg!)
0050: 61 6e 64 20 61 20 63 69 72 63 6c 65 29 2e 0a 62 and a circle)..b
0060: 6f 6f 6c 20 6c 69 6e 65 5f 63 69 72 63 6c 65 28 ool line_circle(
0070: 43 4d 50 20 6c 61 2c 20 43 4d 50 20 6c 62 2c 20 CMP la, CMP lb,
0080: 43 4d 50 20 63 2c 20 64 6f 75 62 6c 65 20 72 2c CMP c, double r,
0090: 20 43 4d 50 2a 20 70 31 2c 20 43 4d 50 2a 20 70 CMP* p1, CMP* p
00a0: 32 29 0a 7b 0a 09 43 4d 50 20 76 20 3d 20 28 6c 2).{..CMP v = (l
00b0: 62 2d 6c 61 29 20 2f 20 61 62 73 28 6c 62 2d 6c b-la) / abs(lb-l
00c0: 61 29 3b 0a 09 43 4d 50 20 6f 20 3d 20 28 63 2d a);..CMP o = (c-
00d0: 6c 61 29 20 2f 20 76 3b 0a 09 69 66 28 20 61 62 la) / v;..if( ab
00e0: 73 28 6f 2e 69 6d 61 67 28 29 29 20 3e 20 72 20 s(o.imag()) > r
00f0: 29 0a 09 09 72 65 74 75 72 6e 20 66 61 6c 73 65 )...return false
0100: 3b 0a 09 64 6f 75 62 6c 65 20 64 78 20 3d 20 73 ;..double dx = s
0110: 71 72 74 28 72 2a 72 20 2d 20 6f 2e 69 6d 61 67 qrt(r*r - o.imag
0120: 28 29 2a 6f 2e 69 6d 61 67 28 29 29 3b 0a 09 2a ()*o.imag());..*
0130: 70 31 20 3d 20 6c 61 20 2b 20 28 6f 2e 72 65 61 p1 = la + (o.rea
0140: 6c 28 29 2d 64 78 29 2a 76 3b 0a 09 2a 70 32 20 l()-dx)*v;..*p2
0150: 3d 20 6c 61 20 2b 20 28 6f 2e 72 65 61 6c 28 29 = la + (o.real()
0160: 2b 64 78 29 2a 76 3b 0a 09 72 65 74 75 72 6e 20 +dx)*v;..return
0170: 74 72 75 65 3b 0a 7d 0a 0a 2f 2f 20 57 68 65 74 true;.}..// Whet
0180: 68 65 72 20 6f 72 20 6e 6f 74 20 7c 70 7c 20 69 her or not |p| i
0190: 73 20 69 6e 20 74 68 65 20 63 69 72 63 6c 65 20 s in the circle
01a0: 28 63 2c 20 72 29 2e 0a 62 6f 6f 6c 20 70 74 5f (c, r)..bool pt_
01b0: 69 6e 5f 63 69 72 63 6c 65 28 43 4d 50 20 70 2c in_circle(CMP p,
01c0: 20 43 4d 50 20 63 2c 20 64 6f 75 62 6c 65 20 72 CMP c, double r
01d0: 29 0a 7b 0a 09 72 65 74 75 72 6e 20 6e 6f 72 6d ).{..return norm
01e0: 28 70 2d 63 29 20 3c 3d 20 72 2a 72 3b 0a 7d 0a (p-c) <= r*r;.}.
01f0: 0a 2f 2f 20 41 73 73 75 6d 69 6e 67 20 7c 6f 7c .// Assuming |o|
0200: 20 69 73 20 6f 75 74 73 69 64 65 20 28 43 2c 72 is outside (C,r
0210: 29 2c 20 63 6f 6d 70 75 74 65 20 74 68 65 20 74 ), compute the t
0220: 77 6f 20 74 61 6e 67 65 6e 74 20 70 6f 69 6e 74 wo tangent point
0230: 73 2e 0a 76 6f 69 64 20 73 65 73 73 65 6e 28 43 s..void sessen(C
0240: 4d 50 20 6f 2c 20 43 4d 50 20 63 2c 20 64 6f 75 MP o, CMP c, dou
0250: 62 6c 65 20 72 2c 20 43 4d 50 2a 20 70 31 2c 20 ble r, CMP* p1,
0260: 43 4d 50 2a 20 70 32 29 0a 7b 0a 09 64 6f 75 62 CMP* p2).{..doub
0270: 6c 65 20 6c 65 6e 20 3d 20 73 71 72 74 28 6e 6f le len = sqrt(no
0280: 72 6d 28 63 2d 6f 29 20 2d 20 72 2a 72 29 3b 0a rm(c-o) - r*r);.
0290: 09 64 6f 75 62 6c 65 20 74 68 65 74 61 20 3d 20 .double theta =
02a0: 61 73 69 6e 28 72 2f 61 62 73 28 63 2d 6f 29 29 asin(r/abs(c-o))
02b0: 3b 0a 0a 09 69 66 28 70 31 29 20 2a 70 31 20 3d ;...if(p1) *p1 =
02c0: 20 6f 2b 28 63 2d 6f 29 2a 70 6f 6c 61 72 28 6c o+(c-o)*polar(l
02d0: 65 6e 2f 61 62 73 28 63 2d 6f 29 2c 20 74 68 65 en/abs(c-o), the
02e0: 74 61 29 3b 0a 09 69 66 28 70 32 29 20 2a 70 32 ta);..if(p2) *p2
02f0: 20 3d 20 6f 2b 28 63 2d 6f 29 2a 70 6f 6c 61 72 = o+(c-o)*polar
0300: 28 6c 65 6e 2f 61 62 73 28 63 2d 6f 29 2c 20 2d (len/abs(c-o), -
0310: 74 68 65 74 61 29 3b 0a 7d 0a 0a 2f 2f 20 46 6f theta);.}..// Fo
0320: 72 20 74 77 6f 20 70 6f 69 6e 74 73 20 7c 70 7c r two points |p|
0330: 20 61 6e 64 20 7c 71 7c 20 6f 6e 20 28 63 2c 72 and |q| on (c,r
0340: 29 2c 20 63 6f 6d 70 75 74 65 20 74 68 65 69 72 ), compute their
0350: 20 64 69 73 74 61 6e 63 65 20 61 6c 6f 6e 67 20 distance along
0360: 74 68 65 20 63 69 72 63 6c 65 2e 0a 64 6f 75 62 the circle..doub
0370: 6c 65 20 64 5f 6f 6e 5f 63 28 43 4d 50 20 63 2c le d_on_c(CMP c,
0380: 20 64 6f 75 62 6c 65 20 72 2c 20 43 4d 50 20 70 double r, CMP p
0390: 2c 20 43 4d 50 20 71 29 0a 7b 0a 09 72 65 74 75 , CMP q).{..retu
03a0: 72 6e 20 61 62 73 28 61 72 67 28 28 70 2d 63 29 rn abs(arg((p-c)
03b0: 20 2f 20 28 71 2d 63 29 29 29 20 2a 20 72 3b 0a / (q-c))) * r;.
03c0: 7d 0a }.