Giúp em giải bài toán tìm số giao điểm của n đường thẳng

[larachang]

Bài toán nó là thế này:
Trên mặt phẳng cho trước n đường thẳng. Hãy viết chương trình tính số giao điểm của n đường thẳng này (Trong n đường thẳng không đồng thời trùng nhau). Yêu cầu tính càng chính xác càng tốt.
Các đường thằng trên mặt phẳng được cho bởi ba số thực A, B, C với phương trình Ax+By+C=0, ở đây các số A, B không đồng thời bằng 0.
Dữ liệu vào: ghi trên tệp GDIEM.INP gồm n+1 dòng.
- Dòng đầu ghi số n (số đường thẳng)
- n dòng tiếp theo, mỗi dòng ghi 3 số thực A, B, C cách nhau bởi dấu cách.
Dữ liệu ra: ghi vào tệp GDIEM.OUT gồm 1 dòng chứa số giao điểm.

Nếu trên rum nhà mình có rồi thì các bác cho e cái link, còn không thì nhờ các bác giải dùm e mới. Cũng không cần phải viết hoàn chỉnh đâu ạ, cho e cái ý tưởng là được rồi. Xin đa tạ trước^^!

[HGMinh95]

Với mỗi đường thẳng bạn kiểm tra xem nó cắt bao nhiêu đường thẳng, sau đó chia cho 2 là được số giao điểm.

[larachang]

Với mỗi đường thẳng bạn kiểm tra xem nó cắt bao nhiêu đường thẳng, sau đó chia cho 2 là được số giao điểm.

Như thế thì có nhiều trường hợp lắm: song song, đồng quy, cắt nhau đôi một. Có thuật toán nào giúp làm nhanh bài này hok ạ?!

[hoctrodauto]

Bạn sử dụng kiến thức hình học vector lớp 12 :D hoặc tính các định thức tương ứng với 3 thông số a, b, c của đường thẳng

Mình có code bên C++ thôi
isCross(Line d,Point &p)
{
double D=A*d.B-d.A*B;
double Dx=-(C*d.B-d.C*B);
double Dy=-(A*d.C-d.A*C);
if (D==0)
{
if (Dx==0 && Dy==0)
{
if (A==0 && B==0 && C!=0) return 0;
return 2;
}
else return 0;
}
else
{
p.x=Dx/D;
p.y=Dy/D;
return 1;
}
}

[HGMinh95]

Như thế thì có nhiều trường hợp lắm: song song, đồng quy, cắt nhau đôi một. Có thuật toán nào giúp làm nhanh bài này hok ạ?!
Quên mất là các đường thẳng có thể đồng quy :)

Theo mình, bạn cứ xét 2 đường thẳng u, v bất kỳ, nếu u, v cắt nhau (tức là a*b'<>b*a') và giao điểm của u, v không trùng với giao điểm của 2 đường thẳng nào được xét trước u, v thì lưu giao điểm này lại (chỉ cần lưu lại đây là giao điểm của 2 đường nào thôi)

Để kiểm tra xem giao điểm này có trùng với giao điểm nào đã xét trước đó chưa, bạn chỉ cần xét 2 hệ pt có tương đương nhau ko
VD: Giao điểm của u, v là nghiệm của hệ
ax + by = c
dx + ey = f
Giao điểm của u', v' là nghiệm của hệ
a'x + b'y = c'
d'x + e'y = f'
Giao điểm của (u,v)=(u',v') <=> ab'c=a'bc' và de'f=d'ef'
Vì không sử dụng phép chia nào lên thuật toán này cho ra kết quả khá chính xác