這道題跟1086是一樣的思路，判斷兩線段是否相交。用跨立實(shí)驗(yàn)即可。

#include<iostream> #include<cstdio> #include<cstring> using namespace std;const int maxn = 100024; struct Segment {double x1,x2,y1,y2; }s[maxn]; int n; bool vis[maxn];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;memset(vis,false,sizeof(vis));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,cnt = 0,sum = 0;for(int i = 1; i < n; i++)for(int j = i + 1; j <= n; j++)if(Segment_Intersection(i,j)){vis[i] = true;cnt++;break;}cnt = n - cnt;printf("Top sticks:");for(int i = 1; i <= n; i++)if(vis[i] == false){sum++;printf(cnt == sum ? " %d.\n":" %d,",i); }}return 0; }

總結(jié)

以上是生活随笔為你收集整理的hdu 1147(线段相交)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。