poj 1410 线段与矩形相交

题意：判断是否线段有和给定的矩形右交点

解法：几何模板题

坑点：

• 不一定就是左上点和右下点

• 线段如果在矩形内也算是相交

1. /************************************************************************* 
2.     > File Name: poj1410.cpp 
3.     > Author: cy 
4.     > Mail: [e-mail]  
5.     > Created Time: 14/11/10 19:38:24 
6.  ************************************************************************/ 
7.  
8. #include<iostream> 
9. #include<cstring> 
10. #include <algorithm> 
11. #include<cstdlib> 
12. #include<vector> 
13. #include<cmath> 
14. #include<stdlib.h> 
15. #include<iomanip> 
16. #include<list> 
17. #include<deque> 
18. #include<map> 
19. #include <stdio.h> 
20. #include <queue> 
21.  
22. const int maxn=1000+5; 
23.  
24. #define inf 0x3f3f3f3f 
25.   #define INF 0x3FFFFFFFFFFFFFFFLL 
26. #define rep(i,n) for(i=0;i<n;i++) 
27.  #define reP(i,n) for(i=1;i<=n;i++) 
28.  
29. #define ull unsigned long long 
30.  #define ll long long 
31.  
32. #define cle(a) memset(a,0,sizeof(a)) 
33.  
34. using namespace std; 
35. double eps= 0.00000001; 
36. struct point  //定义点 
37. { 
38.     double x; 
39.     double y; 
40. }; 
41.  
42.  
43. point operator -(point a,point b) //向量减法 
44. { 
45.     point v; 
46.     v.x=a.x-b.x; 
47.     v.y=a.y-b.y; 
48.     return v; 
49. } 
50.  
51. bool zero(double x) 
52. { 
53.     return fabs(x)<eps?true:false; 
54. } 
55.  
56. double fork_mul(point a,point b) //向量叉积 
57. { 
58.     return (a.x*b.y-a.y*b.x); 
59. } 
60.  
61. double min(double x,double y) 
62. { 
63.     return x<y?x:y; 
64. } 
65.  
66. double max(double x,double y) 
67. { 
68.     return x>y?x:y; 
69. } 
70.  
71. int intersect_sign(point a,point b,point c,point d,point &result) //两线段位置关系的标志 
72. { 
73.     double cba=fork_mul(b-c,a-c); 
74.     double dba=fork_mul(b-d,a-d),v12=fork_mul(b-a,d-c); 
75.     if(zero(v12)==true) //两线段方向相同 
76.     { 
77.         if(zero(cba)==true&&zero(dba)==true) //两线段共线 
78.         { 
79.             if(min(a.x,b.x)<max(c.x,d.x)&&min(c.x,d.x)<max(a.x,b.x)&&min(a.y,b.y)<max(c.y,d.y)&&min(c.y,d.y)<max(a.y,b.y)) 
80.                 return -3; //重叠共线 
81.             if(min(a.x,b.x)>max(c.x,d.x)||min(c.x,d.x)>max(a.x,b.x)||min(a.y,b.y)>max(c.y,d.y)||min(c.y,d.y)>max(a.y,b.y)) 
82.                 return -2; //分离共线 
83.             return -1; //首尾相接 
84.         } 
85.         else 
86.             return 0; //两线段平行 
87.     } 
88.     else //两线段方向不同，它们各自所在的直线相交 
89.     { 
90.         double bdc=fork_mul(d-b,c-b),adc=fork_mul(d-a,c-a); 
91.         result.x=(dba*c.x-cba*d.x)/(dba-cba); //求两线段所在直线的交点 
92.         result.y=(dba*c.y-cba*d.y)/(dba-cba); 
93.         if(dba*cba<=0&&bdc*adc<=0) 
94.             return 1; //线段相交 
95.         else 
96.             return 2; //线段不相交 
97.     } 
98. } 
99. bool getbool(point a,point b,point c)//判断是否在矩形内 
100. { 
101.     int minx=min(b.x,c.x); 
102.     int maxx=max(b.x,c.x); 
103.     int miny=min(b.y,c.y); 
104.     int maxy=max(b.y,c.y); 
105.     if(a.x>=minx&&a.x<=maxx&&a.y>=miny&&a.y<=maxy) 
106.     { 
107.         return true; 
108.     } 
109.     return false; 
110. } 
111. int main() 
112. { 
113. #ifndef ONLINE_JUDGE 
114.      freopen("in.txt","r",stdin); 
115.      //freopen("out.txt","w",stdout); 
116. #endif 
117.     int n; 
118.     cin>>n; 
119.     while(n--) 
120.     { 
121.         point be,en;//线段的起点和终点 
122.         scanf("%lf%lf%lf%lf",&be.x,&be.y,&en.x,&en.y); 
123.         point upleft,downright,upright,downleft; 
124.         scanf("%lf%lf%lf%lf",&upleft.x,&upleft.y,&downright.x,&downright.y); 
125.         if(getbool(be,upleft,downright)||getbool(en,upleft,downright)) 
126.         { 
127.             cout<<"T"<<endl; 
128.             continue; 
129.         } 
130.         downleft.x=downright.x;downleft.y=upleft.y; 
131.         upright.x=upleft.x;upright.y=downright.y; 
132.         point temp; 
133.         if(intersect_sign(be,en,upleft,upright,temp)%2==1||intersect_sign(be,en,upleft,downleft,temp)%2==1||intersect_sign(be,en,downleft,downright,temp)%2==1||intersect_sign(be,en,upright,downright,temp)%2==1) 
134.         { 
135.             cout<<"T"<<endl; 
136.         } 
137.         else{ 
138.             cout<<"F"<<endl; 
139.         } 
140.     } 
141.     return 0; 
142. }