首页 > 代码库 > POJ 1410 Intersection(线段相交&&判断点在矩形内&&坑爹)
POJ 1410 Intersection(线段相交&&判断点在矩形内&&坑爹)
Intersection
大意:给你一条线段,给你一个矩形,问是否相交。
相交:线段完全在矩形内部算相交;线段与矩形任意一条边不规范相交算相交。
思路:知道具体的相交规则之后题其实是不难的,但是还有个坑点就是题目里明明说给的是矩形左上角跟右下角的点,但实际上不是,需要重新判断一下...真坑。
1 struct Point 2 { 3 double x, y; 4 } A, B, C, D; 5 struct Line 6 { 7 Point a, b; 8 } L; 9 10 int n;11 12 double xmult(Point p1, Point p2, Point p)13 {14 return (p1.x-p.x)*(p2.y-p.y)-(p2.x-p.x)*(p1.y-p.y);15 }16 17 ///若共线,返回1;不共线,返回0。18 int dot_inLine(Point p1, Point p2, Point p3){19 return zero(xmult(p1, p2, p3));20 }21 ///判两点在线段同侧,点在线段上返回022 int same_side(Point p1, Point p2, Line l){23 return xmult(l.a, p1, l.b)*xmult(l.a, p2, l.b) > eps;24 }25 ///判点是否在线段上,包括端点26 int dot_onLine_in(Point p, Line l){27 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;28 }29 int intersect_in(Line u, Line v){30 if (!dot_inLine(u.a, u.b, v.a)31 || !dot_inLine(u.a, u.b, v.b))32 return !same_side(u.a, u.b,v) && !same_side(v.a, v.b,u);33 return dot_onLine_in(u.a, v) || dot_onLine_in(u.b, v)34 || dot_onLine_in(v.a, u) || dot_onLine_in(v.b, u);35 }36 37 bool is_Inter(Point A, Point B, Point C, Point D, Point t)38 {39 if(xmult(t, A, B) > eps && xmult(t, B, C) > eps && xmult(t, C, D) > eps && xmult(t, D, A) > eps)40 return true;41 if(xmult(t, A, B) < eps && xmult(t, B, C) < eps && xmult(t, C, D) < eps && xmult(t, D, A) < eps)42 return true;43 if(t.x >= A.x && t.x <= B.x && t.y >= C.y && t.y <= B.y && (zero(xmult(t, A, B)) || zero(xmult(t, B, C)) || zero(xmult(t, C, D)) || zero(xmult(t, D, A))))44 return true;45 return false;46 }47 48 int T;49 50 void Solve()51 {52 scanf("%d", &T);53 while(T--)54 {55 scanf("%lf%lf%lf%lf%lf%lf%lf%lf", &L.a.x, &L.a.y, &L.b.x, &L.b.y, &C.x, &C.y, &D.x, &D.y);56 A.x = min(C.x, D.x);57 A.y = max(C.y, D.y);58 C.x = max(C.x, D.x);59 C.y = min(C.y, D.y);60 B.x = C.x, B.y = A.y;61 D.x = A.x, D.y = C.y;62 if(is_Inter(A, B, C, D, L.a) && is_Inter(A, B, C, D, L.b))63 {64 printf("T\n");65 }66 else if(intersect_in((Line){A, B}, L) || intersect_in((Line){B, C,}, L) || intersect_in((Line){C, D}, L) || intersect_in((Line){D, A}, L))67 {68 printf("T\n");69 }70 else71 {72 printf("F\n");73 }74 }75 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。