POJ 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 //更多精彩内容:http://www.bianceng.cnhttp://www.bianceng.cn/Programming/sjjg/ 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", n); } }
以上是小编为您精心准备的的内容,在的博客、问答、公众号、人物、课程等栏目也有的相关内容,欢迎继续使用右上角搜索按钮进行搜索int
, return
, poj
, chrry pick
, point
, 在线
, STICKS
, 100010
, 线段交点算法
, 线段交点
最后
poj2653、求两条线段的交点、线段交点、线段与圆的交点、求两线段交点,以便于您获取更多的相关知识。