Giao điểm của đường tròn và đường thẳng

Bạn nào có thuật toán tìm giao điểm cuả đường tròn và đường thẳng send cho mình nha.
số là thế này: mình có đoạn thẳng AB và pt đường tròn. bi h mình muốn bít . cái ông đường tròn đó có cắt đường thẳng không?

Cái này chắc là dựa vào công thức toán học mà làm thui. Lấy tập Hình học giải tích ra xem lại thử coi. Tui nhớ hình như có đó.

Mình đã tìm ra thuật toán. thế này: đầu tiên viết pt đường thẳng AB (theo tham số t). thế pt đó vào pt đường tròn nếu tìm được t thì thay vào pt AB ta tìm được toạ độ giao điểm. xong rồi kiêm tra xem toạ độ này có năm trong đoaạn thẳng AB hay ko. nếu có thì CẮT, cái naỳ nếu giải trong giấy thi quá dễ dàng. nhưng đưa cho computer no giai. ko dễ chút nào. mình post bài này lên. vì đây là một trong những kiến thức cơ bản để học môn Dồ Hoạ Máy Tính.
có một bài toán liên quan đến phần này các bạn tham khảo:
"cho tam giác ABC và một điểm M không nằn trên ba cạnh của tam giác. vít ct tìm số lớn nhất K sao cho đường tròn (M,K) không cắt bất cứ cạnh nào, và không chứa tam giác"
tríchL Đề thi Olympic tin hoc khối không chuyên 2002
Input.txt: toa độ lần lượt 4 diểm A, B, C, M
Output.txt: R
------------------------------
ý tưởng thuật toán: tính khoảng cách từ M đến A, B, C và 3 đoạn thẳng AB,Ac,Bc
ta có 6 R. mỗi R ta kiểm tra xem (M,R) ko cắt 3 cạnh tam giác và ko chứa A, B, C thì đó là kết quả cần tim
------------------------------
#include<fstream>
#include<cmath>

using namespace std;

const char fi[] = "TRIANGLE.INP";
const char fo[] = "TRIANGLE.OUT";

struct point
{
double x,y;
};

point A, B, C, M;
double dis;

void readfile()
{
ifstream fin;
fin.open(fi);
fin>>A.x>>A.y;
fin>>B.x>>B.y;
fin>>C.x>>C.y;
fin>>M.x>>M.y;
fin.close();
}

void writefile()
{
ofstream fout;
fout.open(fo);
int idis = dis *10;
dis = (double)idis/10;
fout<<(double)dis;
fout.close();
}

double distance_point_point( point A, point B) // khoang cach hai diem
{
return sqrt( pow(A.x - B.x, 2) + pow(A.y - B.y, 2) );
}

bool point_in_segment_line(point M, point A, point B) // kiem tra diem M co thuoc doan AB khong
{
double nho = 0.000000001;
return( distance_point_point(A,M) + distance_point_point(M,B)
- distance_point_point(A,B) <= nho );
}

double distance_point_segment_line( point M, point A, point B )
{
point v,gd;
float a, b, c,t;

// v la vec to chi phuong
v.x = -1*(A.y - B.y);
v.y = A.x - B.x;

// Phuong trinh duong thang AB: ax + by +c = 0
a = A.y - B.y;
b = B.x - A.x;
c = A.x*B.y - A.y*B.x;

float ms = a*v.x+b*v.y;
if (ms!=0)
t = -1*( (c+a*M.x+b*M.y)/(ms) );

// gd la giao diem cua duong cao ke tu M xuong duong thang AB
gd.x = M.x + t*v.x;
gd.y = M.y + t*v.y;

if( point_in_segment_line(gd, A, B) )
{
return distance_point_point(gd, M);
}

float dis1, dis2;
dis1 = distance_point_point(A,M);
dis2 = distance_point_point(B,M);

if( dis1 > dis2 )
{
dis1 = dis2;
}
return dis1;
}



bool point_in_circle( point M, point O, double R ) // kiem tra diem M co nam trong duong tron khong
{
return(pow((M.x - O.x),2) + pow((M.y - O.y),2) - pow(R,2) <= 0);
}

// kiem tra xem doan thang AB co cat duong tron khong?
bool segment_cut_circle( point A, point B, point O, double R )
{
if( distance_point_segment_line( O, A, B ) >= R )
return 0;
// tim toa do giao diem
point v, gd;
v.x = A.x - B.x;
v.y = A.y - B.y;
double t1,t2,a, b, c, delta_phay; // b: b phay
a = v.x*v.x + v.y*v.y;
b = A.x*v.x - v.x*O.x + A.y*v.y - v.y*O.y;
c = A.x*A.x + A.y*A.y + O.x*O.x + O.y*O.y - R*R - 2*A.x*O.x -2*A.y*O.y;

delta_phay = b*b - a*c;
if( delta_phay>0 )
{
t1 = (-1*b +sqrt(delta_phay))/a;
gd.x = A.x + v.x*t1;
gd.y = A.y + v.y*t1;
if( point_in_segment_line(gd, A, B) )
return 1;

t2 = (-1*b -sqrt(delta_phay))/a;
gd.x = A.x + v.x*t2;
gd.y = A.y + v.y*t2;
if( point_in_segment_line(gd, A, B) )
return 1;
}
return 0;
}

void process() // xu ly
{
dis = distance_point_point( M, A );

///////////////////////////// kiem tra diem

if( (!segment_cut_circle(A,B,M,dis)) && (!segment_cut_circle(A,C,M,dis))
&& (!segment_cut_circle(B,C,M,dis))
&& (!point_in_circle(B,M,dis) && (!point_in_circle(C,M,dis)))
)
return;
//
dis = distance_point_point( M, B );
if( (!segment_cut_circle(A,B,M,dis)) && (!segment_cut_circle(A,C,M,dis))
&& (!segment_cut_circle(B,C,M,dis))
&& (!point_in_circle(A,M,dis) && (!point_in_circle(C,M,dis)))
)
return;
//
dis = distance_point_point( M, C );
if( (!segment_cut_circle(A,B,M,dis)) && (!segment_cut_circle(A,C,M,dis))
&& (!segment_cut_circle(B,C,M,dis))
&& (!point_in_circle(B,M,dis) && (!point_in_circle(A,M,dis)))
)
return;

///////////////////////////// kiem tra doan

dis = distance_point_segment_line( M, A, B );
if( (!segment_cut_circle(A,C,M,dis)) && (!segment_cut_circle(B,C,M,dis))
&& (!point_in_circle(A,M,dis))&& (!point_in_circle(B,M,dis))&& (!point_in_circle(C,M,dis))
)
return;
//
dis = distance_point_segment_line( M, A, C );
if( (!segment_cut_circle(A,B,M,dis)) && (!segment_cut_circle(B,C,M,dis))
&& (!point_in_circle(A,M,dis))&& (!point_in_circle(B,M,dis))&& (!point_in_circle(C,M,dis))
)
return;
//
dis = distance_point_segment_line( M, B, C );
if( (!segment_cut_circle(A,C,M,dis)) && (!segment_cut_circle(A,B,M,dis))
&& (!point_in_circle(A,M,dis))&& (!point_in_circle(B,M,dis))&& (!point_in_circle(C,M,dis))
)
return;
dis = -1;
}

void main()
{
readfile();
process();
writefile();
}

hic, nhìn vô hổng hiểu gì hết trơn hết