题目链接：http://acm.hdu.edu.cn/showPRoblem.php?pid=2150 题意：给你n条管子，问你他们之间是否有交点，管子由k条线段组成 解析：理解题意乱搞就好，很无语的是，判线段交点的时候，叉乘会爆int！叉乘会爆int！叉乘会爆int，我的代码真是又臭又长O__O “…
#include <cmath>#include <algorithm>#include <iostream>#include <cstdio>#include <vector>#include <cstring>#include <stack>using namespace std;const int maxn = 1005+10;const double eps = 1e-5;struct point{ int x; int y;}a[maxn];struct line{ point a; point b;};struct pipe{ line l[1005]; int cnt;}b[maxn];long long x_mul(point p0,point p1,point p2){ return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);}int dot_online(point p1,line t){ return x_mul(p1,t.a,t.b);}bool judge(line t1,line t2){ //排斥实验 bool flag1 = min(t1.a.x,t1.b.x)<=max(t2.a.x,t2.b.x) &&min(t2.a.x,t2.b.x)<=max(t1.a.x,t1.b.x) &&min(t1.a.y,t1.b.y)<=max(t2.a.y,t2.b.y) &&min(t2.a.y,t2.b.y)<=max(t1.a.y,t1.b.y); //跨立实验 bool flag2 = (x_mul(t1.a,t2.a,t2.b)*x_mul(t1.b,t2.a,t2.b)<=0) &&(x_mul(t2.a,t1.a,t1.b)*x_mul(t2.b,t1.a,t1.b)<=0); return flag1&&flag2;}int main(void){ int n; while(~scanf("%d",&n)) { memset(b,0,sizeof(b)); for(int i=0;i<n;i++) { int m; scanf("%d",&m); for(int j=0;j<m;j++) scanf("%d %d",&a[j].x,&a[j].y); for(int j=0;j<m-1;j++) { b[i].l[j].a = a[j]; b[i].l[j].b = a[j+1]; } b[i].cnt = m-1; } int flag = false; for(int i=0;i<n;i++) { for(int j=i+1;j<n;j++) { for(int l=0;l<b[i].cnt;l++) { for(int k=0;k<b[j].cnt;k++) { if(judge(b[i].l[l],b[j].l[k])) { flag = true; break; } } if(flag) break; } if(flag) break; } if(flag) break; } if(flag) puts("Yes"); else puts("No"); } return 0;}新闻热点
疑难解答
