題意：給你n條線段依次放到二維平面上，問最后有哪些沒與前面的線段相交，即它是頂上的線段

?

題解：數(shù)據(jù)弱，正向純模擬可過

但是有一個陷阱：如果我們從后面向前枚舉，找與前面哪些相交，再刪除前面那些相交的線段，這樣就錯了

因為如果線段8與5，6，7相交了，我們接下來不能直接判斷4，我們還要找7,6,5與之前哪些相交

?

#include<set> #include<map> #include<queue> #include<stack> #include<cmath> #include<vector> #include<string> #include<cstdio> #include<cstring> #include<iomanip> #include<stdlib.h> #include<iostream> #include<algorithm> using namespace std; #define eps 1E-8 /*注意可能會有輸出-0.000*/ #define Sgn(x) (x<-eps? -1 :x<eps? 0:1)//x為兩個浮點數(shù)差的比較,注意返回整型 #define Cvs(x) (x > 0.0 ? x+eps : x-eps)//浮點數(shù)轉(zhuǎn)化 #define zero(x) (((x)>0?(x):-(x))<eps)//判斷是否等于0 #define mul(a,b) (a<<b) #define dir(a,b) (a>>b) typedef long long ll; typedef unsigned long long ull; const int Inf=1<<28; const ll INF=1ll<<60; const double Pi=acos(-1.0); const int Mod=1e9+7; const int Max=100010; struct point {double x,y; }; struct line {point a,b; }; double xmult(point p1,point p2,point p0) {return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y); } int isIntersected(point p1,point p2,point l1,point l2) {return (max(p1.x,p2.x)>=min(l1.x,l2.x)) &&(max(p1.y,p2.y)>=min(l1.y,l2.y)) &&(max(l1.x,l2.x)>=min(p1.x,p2.x)) &&(max(l1.y,l2.y)>=min(p1.y,p2.y)) &&(xmult(l1,p2,p1)*xmult(p2,l2,p1)>0) &&(xmult(p1,l2,l1)*xmult(l2,p2,l1)>0) ; } line sti[Max]; int ans[Max],vis[Max]; int Solve(int n) {int coun=0;for(int i=1;i<=n;++i){for(int j=i+1;j<=n;++j){if(isIntersected(sti[i].a,sti[i].b,sti[j].a,sti[j].b)){vis[i]=0;break;}}}for(int i=n;i;--i)if(vis[i])ans[coun++]=i;return coun; } int main() {int n;while(~scanf("%d",&n)&&n){for(int i=1;i<=n;++i){scanf("%lf %lf %lf %lf",&sti[i].a.x,&sti[i].a.y,&sti[i].b.x,&sti[i].b.y);vis[i]=1;}int coun=Solve(n);printf("Top sticks: ");for(int i=coun-1;~i;--i){printf("%d%s",ans[i],i?", ":".\n");}}return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/zhuanzhuruyi/p/6032257.html

總結(jié)

以上是生活随笔為你收集整理的POJ 2653 Pick-up sticks （线段相交）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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