首页 > 其他 > 详细

POJ 1410 Intersection(线段相交&&判断点在矩形内&&坑爹)

时间:2014-06-28 10:36:42      阅读:251      评论:0      收藏:0      [点我收藏+]

Intersection

 

大意:给你一条线段,给你一个矩形,问是否相交。

    相交:线段完全在矩形内部算相交;线段与矩形任意一条边不规范相交算相交。

思路:知道具体的相交规则之后题其实是不难的,但是还有个坑点就是题目里明明说给的是矩形左上角跟右下角的点,但实际上不是,需要重新判断一下...真坑。

bubuko.com,布布扣
 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 ///判两点在线段同侧,点在线段上返回0
22 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         else
71         {
72             printf("F\n");
73         }
74     }
75 }
POJ 1410

 

POJ 1410 Intersection(线段相交&&判断点在矩形内&&坑爹),布布扣,bubuko.com

POJ 1410 Intersection(线段相交&&判断点在矩形内&&坑爹)

原文:http://www.cnblogs.com/Silence-AC/p/3804164.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!