題意：給出一些線段，問有多少個交點。

解題思路：這里實際就是一個線段相交的模型，下面這個圖給出了思路。

如果兩線段相交，則兩線段必然相互跨立對方。若P1P2跨立Q1Q2 ，則矢量 ( P1 - Q1 ) 和( P2 - Q1 )位于矢量( Q2 - Q1 ) 的兩側，即( P1 - Q1 ) × ( Q2 - Q1 ) * ( P2 - Q1 ) × ( Q2 - Q1 ) < 0。上式可改寫成( P1 - Q1 ) × ( Q2 - Q1 ) * ( Q2 - Q1 ) × ( P2 - Q1 ) > 0。當 ( P1 - Q1 ) × ( Q2 - Q1 ) = 0 時，說明 ( P1 - Q1 ) 和 ( Q2 - Q1 )共線，但是因為已經通過快速排斥試驗，所以 P1 一定在線段 Q1Q2上；同理，( Q2 - Q1 ) ×(P2 - Q1 ) = 0 說明 P2 一定在線段 Q1Q2上。所以判斷P1P2跨立Q1Q2的依據是：( P1 - Q1 ) × ( Q2 - Q1 ) * ( Q2 - Q1 ) × ( P2 - Q1 ) >= 0。同理判斷Q1Q2跨立P1P2的依據是：( Q1 - P1 ) × ( P2 - P1 ) * ( P2 - P1 ) × ( Q2 - P1 ) >= 0。具體情況如下圖所示：

在實際寫的時候并沒有先去判斷快速排斥實驗，而是直接使用跨立實驗。注意，這里跨立實驗要判斷兩次， 不僅P1P2一次，Q1Q2也要一次。

#include<iostream> #include<cstdio> #include<cstring> using namespace std;const int maxn = 105; struct Segment {double x1,x2,y1,y2; }s[maxn]; int n;bool Segment_Intersection(int i,int j) {double s1 = (s[i].x1 - s[j].x1) * (s[i].y1 - s[i].y2) - (s[i].x1 - s[i].x2) * (s[i].y1 - s[j].y1);double s2 = (s[i].x1 - s[j].x2) * (s[i].y1 - s[i].y2) - (s[i].x1 - s[i].x2) * (s[i].y1 - s[j].y2);if(s1 * s2 > 0) return false;double s3 = (s[j].x1 - s[i].x1) * (s[j].y1 - s[j].y2) - (s[j].x1 - s[j].x2) * (s[j].y1 - s[i].y1);double s4 = (s[j].x1 - s[i].x2) * (s[j].y1 - s[j].y2) - (s[j].x1 - s[j].x2) * (s[j].y1 - s[i].y2);if(s3 * s4 > 0) return false;return true; }int main() {while(scanf("%d",&n)!=EOF){if(n == 0) break;for(int i = 1; i <= n; i++)scanf("%lf%lf%lf%lf",&s[i].x1,&s[i].y1,&s[i].x2,&s[i].y2);int ans = 0;for(int i = 1; i < n; i++)for(int j = i + 1; j <= n; j++)if(Segment_Intersection(i,j))ans++;printf("%d\n",ans);}return 0; }

總結

以上是生活随笔為你收集整理的hdu 1086(判断两线段是否相交)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。