本文主要是介绍poj 1127 Jack Straws (人生第一道计算几何)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
虽然只是对着书敲了一边，但是1A了，
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
double EPS =1e-10;
#define N 14
int n;double add(double a,double b){if(abs(a+b)<EPS*(abs(a)+abs(b))) return 0;return a+b;
}struct P{double x,y;P(){}P(double x,double y):x(x),y(y){}P operator + (P p) {return P(add(x,p.x),add(y,p.y));}P operator - (P p) {return P(add(x,-1.0*p.x),add(y,-1.0*p.y));}P operator * (double d){return P(x*d,y*d);}double dot(P p){return add (x*p.x,y*p.y);}double det(P p){return add(x*p.y, -1.0*y*p.x);}
};bool on_seg(P p1,P p2,P q){return (p1-q).det(p2-q)==0&&(p1-q).dot(p2-q)<=0;
}P intersection(P p1,P p2,P q1,P q2){return p1 + (p2 - p1)*((q2-q1).det(q1-p1)/(q2-q1).det(p2-p1));}P p[N],q[N];
bool g[N][N];void slove(){memset(g,false,sizeof(g));for(int i=1;i<=n;i++){g[i][i]=true;for(int j=1;j<i;j++){if((p[i]-q[i]).det(p[j]-q[j])==0){g[i][j]=g[j][i]=on_seg(p[i],q[i],p[j])||on_seg(p[i],q[i],q[j])||on_seg(p[j],q[j],p[i])||on_seg(p[j],q[j],q[i]);}else {P r=intersection(p[i],q[i],p[j],q[j]);g[i][j]=g[j][i]=on_seg(p[i],q[i],r)&&on_seg(p[j],q[j],r);}}}for(int k=1;k<=n;k++){for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){g[i][j]|=g[i][k]&&g[k][j];}}}
}int main(){while(scanf("%d",&n),n){for(int i=1;i<=n;i++){scanf("%lf%lf%lf%lf",&p[i].x,&p[i].y,&q[i].x,&q[i].y);}slove();int a,b;/*for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){printf("%d ",g[i][j]);}puts("");}*/while(scanf("%d%d",&a,&b)&&a+b){if(g[a][b])puts("CONNECTED");elseputs("NOT CONNECTED");}
}
}这篇关于poj 1127 Jack Straws (人生第一道计算几何)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
