首页 / 软件开发 / 数据结构与算法 / POJ 2653 Pick-up sticks：计算几何 求线段交点

POJ 2653 Pick-up sticks：计算几何 求线段交点2015-02-17POJ 2653：http://poj.org/problem？id=2653

题意：题意很简单，就是在地上按顺序撒一对木棒，看最后有多少是被压住的，输出没有被压住的木棒的序号。有点坑的就是没说清楚木棒怎么算压住，也不知道是不是规范相交。。。我就判断了一下包括端点重合跟部分相交的。

思路：一开始我想的是从后往前遍历，找到每一条边，看他是不是压到之前的边了，如果压到了，就把之前的变标记一下，最后统计没被标记过的，但是TLE了。。。就只能从前面开始找，遍历每一条边是否被后面的压过了，压过了就直接break，如果都没压到，存这条边，最后输出。

int n; struct point{double x, y;} ; struct line{point a, b;} L[100010]; int Ans[100010]; double xmult（point p1, point p2, point p）{return （p1.x-p.x）*（p2.y-p.y） - （p2.x-p.x）*（p1.y-p.y）;} ///判三点共线int dots_inline（point p1,point p2,point p3）{return zero（xmult（p1,p2,p3））;} ///判两点在线段同侧,点在线段上返回0//int same_side（point p1,point p2,line l）{return xmult（l.a,p1,l.b）*xmult（l.a,p2,l.b）>eps;} ///判点是否在线段上,包括端点int dot_online_in（point p,line l）{return zero（xmult（p,l.a,l.b））&&（l.a.x-p.x）*（l.b.x-p.x）<eps&&（l.a.y-p.y）*（l.b.y-p.y）<eps;} ///判两线段相交,包括端点和部分重合int intersect_in（line u,line v）{if （！dots_inline（u.a,u.b,v.a）||！dots_inline（u.a,u.b,v.b））return ！same_side（u.a,u.b,v）&&！same_side（v.a,v.b,u）;return dot_online_in（u.a,v）||dot_online_in（u.b,v）||dot_online_in（v.a,u）||dot_online_in（v.b,u）;} void Solve（）{while（~scanf（"%d", &n） && n）{for（int i = 0; i < n; ++i）{scanf（"%lf%lf%lf%lf", &L[i].a.x, &L[i].a.y, &L[i].b.x, &L[i].b.y）;}int t = 0;for（int i = 0; i < n; ++i）{bool flag = true;for（int j = i+1; j < n; ++j）{if（intersect_in（L[i], L[j]））{flag = false;break;}}if（flag）{Ans[t++] = i+1;}}printf（"Top sticks:"）;for（int i = 0; i < t-1; ++i）{printf（" %d,", Ans[i]）;}printf（" %d.
", n）;}}

From：cnblogs GLSilence