枚舉每條線段 這條線段上面沒有與它相交的線段

#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #define eps 1e-8 #define INF 1e9 using namespace std;const int maxn=200000+10; int ans[1005]; int n,cnt;typedef struct Point {double x,y;Point() {};Point(double xx,double yy){x=xx;y=yy;} } Vector;int sgn(double x) {if(fabs(x) < eps)return 0;if(x < 0)return -1;else return 1; }Point pot[maxn];double crs_prdct(Vector a,Vector b) {return a.x*b.y-b.x*a.y; }Vector operator - (Point a,Point b) {return Vector(a.x-b.x,a.y-b.y); }int intersect(Point p1,Point p2,Point q1,Point q2) {returnmax(p1.x,p2.x) >= min(q1.x,q2.x) &&max(q1.x,q2.x) >= min(p1.x,p2.x) &&max(p1.y,p2.y) >= min(q1.y,q2.y) &&max(q1.y,q2.y) >= min(p1.y,p2.y) &&sgn(crs_prdct(q1-p1,p2-p1))*sgn(crs_prdct(q2-p1,p2-p1)) <= 0 &&sgn(crs_prdct(p1-q1,q2-q1))*sgn(crs_prdct(p2-q1,q2-q1)) <= 0; }int main() { // freopen("in.txt","r",stdin);while(scanf("%d",&n),n){double x1,y1,x2,y2;for(int i=0; i<n; i++){scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);pot[2*i]=Point(x1,y1);pot[2*i+1]=Point(x2,y2);}cnt=0;for(int i=0; i<n; i++){bool flag=true;for(int j=i+1; j<n; j++){if(intersect(pot[2*i],pot[2*i+1],pot[2*j],pot[2*j+1])){flag=false;break;}}if(flag) ans[cnt++]=i+1;if(cnt>1000) break;}sort(ans,ans+cnt);printf("Top sticks:");for(int i=0; i<cnt-1; i++)printf(" %d,",ans[i]);printf(" %d.\n",ans[cnt-1]);}return 0; }

?

轉載于:https://www.cnblogs.com/pach/p/7212221.html

總結

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

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