好贷网好贷款

POJ 2653 Pick-up sticks 计算几何 线段相交

发布时间:2016-12-5 16:39:35 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"POJ 2653 Pick-up sticks 计算几何 线段相交",主要涉及到POJ 2653 Pick-up sticks 计算几何 线段相交方面的内容,对于POJ 2653 Pick-up sticks 计算几何 线段相交感兴趣的同学可以参考一下。

计算几何的题目   庆幸不用判断共线  题目说了    第一种方法是读入一个处理一个   结果超时了 第二种方法是读完了后再处理    AC     同样是暴力求解  但是也得讲究技术啊 TLE代码: #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #define Max 100005 #define eps 1e-10 using namespace std; int v[Max];//标记每层的有多少木棍 typedef struct { double x,y; }point; typedef struct { point a,b; int n;//标记在第几层 }line; line stick[Max]; double multi(point p0, point p1, point p2) { return ( p1.x - p0.x )*( p2.y - p0.y )-( p2.x - p0.x )*( p1.y - p0.y ); } bool isIntersected(point s1,point e1, point s2,point e2) { return (max(s1.x,e1.x) >= min(s2.x,e2.x)) && (max(s2.x,e2.x) >= min(s1.x,e1.x)) && (max(s1.y,e1.y) >= min(s2.y,e2.y)) && (max(s2.y,e2.y) >= min(s1.y,e1.y)) && (multi(s1,s2,e1)*multi(s1,e1,e2)>0) && (multi(s2,s1,e2)*multi(s2,e2,e1)>0); } int main() { #ifdef LOCAL freopen("in.txt","r",stdin); #endif // LOCAL int N; while((scanf("%d",&N),N)) { int Maxn = 1; memset(v,0,sizeof(v)); for(int i = 0; i < N; i++)//读入一个处理一个 { scanf("%lf%lf%lf%lf",&stick[i].a.x,&stick[i].a.y,&stick[i].b.x,&stick[i].b.y); stick[i].n = 1; for(int j = i-1; j >= 0; j--) { if(isIntersected(stick[i].a,stick[i].b,stick[j].a,stick[j].b)) stick[i].n = stick[j].n + 1;//相交在它的上面一层 if(stick[i].n > Maxn) {Maxn++;break;} } v[stick[i].n]++; } printf("Top sticks:"); int t = 1; for(int i = 0; i < N&&t <=v[Maxn]; i++)//最顶层的木棒数 if(stick[i].n == Maxn) { if(t < v[Maxn]){printf(" %d,",i+1);t++;} else {printf(" %d.\n",i+1);t++;} } } return 0; } 下面是AC代码 #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #define Max 100005 #define eps 1e-10 using namespace std; int v[Max];//标记每层的有多少木棍 typedef struct { double x,y; }point; typedef struct { point a,b; }line; line stick[Max]; double multi(point p0, point p1, point p2) { return ( p1.x - p0.x )*( p2.y - p0.y )-( p2.x - p0.x )*( p1.y - p0.y ); } bool isIntersected(point s1,point e1, point s2,point e2) { return (max(s1.x,e1.x) >= min(s2.x,e2.x)) && (max(s2.x,e2.x) >= min(s1.x,e1.x)) && (max(s1.y,e1.y) >= min(s2.y,e2.y)) && (max(s2.y,e2.y) >= min(s1.y,e1.y)) && (multi(s1,s2,e1)*multi(s1,e1,e2)>0) && (multi(s2,s1,e2)*multi(s2,e2,e1)>0); } int main() { #ifdef LOCAL freopen("in.txt","r",stdin); #endif // LOCAL int N; while((scanf("%d",&N),N)) { for(int i = 0;i < N; i++)v[i] = 0; for(int i = 0; i < N; i++)//读入一个处理一个 scanf("%lf%lf%lf%lf",&stick[i].a.x,&stick[i].a.y,&stick[i].b.x,&stick[i].b.y); for(int i = 0; i < N; i++) // 从头扫到尾 只需一遍判断 for(int j = i+1; j < N; j++) { if(isIntersected(stick[i].a,stick[i].b,stick[j].a,stick[j].b)) {v[i] = 1;break;}//标记不是在最上面一层 } printf("Top sticks:"); int t = N-1; while(v[t]) t--; for(int i = 0; i <= t; i++) if(v[i]== 0) { if(i < t)printf(" %d,",i+1);//最顶层的木棒数 else printf(" %d.\n",i+1); } } return 0; }   

上一篇:EditText的 android:imeOptions属性,响应事件
下一篇:简单易用的div弹出层

相关文章

相关评论