http://poj.org/problem?id=1410

???? 給定一個矩形和一條線段，求線段能否交矩形，線段與矩形的邊或矩形內部有交點即為交。

??? 很簡單的一道判斷線段相交的題目，不過要正確理解題目意思：相交要包括矩形的內部，即線段在矩形內部也是True。（The rectangle consists of four straight lines and the area in between.）題目說的左上、右下并非座標中的位置，數據給的點也會是左下、右上！！！（The terms top left and bottom right do not imply any ordering of coordinates. ）

#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
using namespace std;
struct point
{
?double x,y;
}p[10];
double multi(point p0,point p1,point p2)
{
?return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
}
bool is(point s1,point e1,point s2,point e2)
{
?return (max(s1.x,e1.x)>=min(s2.x,e2.x))&&
???(max(s2.x,e2.x)>=min(s1.x,e1.x))&&
???(max(s1.y,e1.y)>=min(s2.y,e2.y))&&
???(max(s2.y,e2.y)>=min(s1.y,e1.y))&&
???(multi(s1,s2,e1)*multi(s1,e1,e2)>=0)&&
???(multi(s2,s1,e2)*multi(s2,e2,e1)>=0);
}
int main()
{
?int cas,i,flag;
?double maxx,maxy,minx,miny;
?scanf("%d",&cas);
?while(cas--)
?{
??for(i=0;i<4;i++)
??scanf("%lf%lf",&p[i].x,&p[i].y);
??p[4].x=p[3].x;
??p[4].y=p[2].y;
??p[5].x=p[2].x;
??p[5].y=p[3].y;
??flag=1;
??if(is(p[0],p[1],p[2],p[5])||is(p[0],p[1],p[5],p[3])||is(p[0],p[1],p[3],p[4])||is(p[0],p[1],p[4],p[2]))
??flag=0;
??maxx=max(p[2].x,p[3].x);
??maxy=max(p[2].y,p[3].y);
??minx=min(p[2].x,p[3].x);
??miny=min(p[2].y,p[3].y);
??if(p[0].x>=minx&&p[0].x<=maxx&&p[0].y>=miny&&p[0].y<=maxy)
??flag=0;
??if(flag)
??cout<<"F"<<endl;
??else
??cout<<"T"<<endl;
?}?
?return 0;
}
??測試數據：

???

68
4 9 11 2 1 1 7 5
11 2 4 9 1 1 7 5
12 12 24 24 19 5 25 17
4 6 15 9 1 1 11 11
19 5 25 17 12 12 24 24
0 18 8 12 1 1 11 11
2 4 4 2 1 1 11 11
-4 9 -11 2 -1 1 -7 5
-11 2 -4 9 -1 1 -7 5
-12 12 -24 24 -19 5 -25 17
-4 6 -15 9 -1 1 -11 11
-19 5 -25 17 -12 12 -24 24
0 18 -8 12 -1 1 -11 11
-2 4 -4 2 -1 1 -11 11
4 -9 11 -2 1 -1 7 -5
11 -2 4 -9 1 -1 7 -5
12 -12 24 -24 19 -5 25 -17
4 -6 15 -9 1 -1 11 -11
19 -5 25 -17 12 -12 24 -24
0 -18 8 -12 1 -1 11 -11
2 -4 4 -2 1 -1 11 -11
-4 -9 -11 -2 -1 -1 -7 -5
-11 -2 -4 -9 -1 -1 -7 -5
-12 -12 -24 -24 -19 -5 -25 -17
-4 -6 -15 -9 -1 -1 -11 -11
-19 -5 -25 -17 -12 -12 -24 -24
0 -18 -8 -12 -1 -1 -11 -11
-2 -4 -4 -2 -1 -1 -11 -11
9 1 9 2 4 3 9 6
9 2 9 1 4 3 9 6
10 3 13 3 4 3 9 6
13 3 10 3 4 3 9 6
10 6 14 6 4 3 9 6
14 6 10 6 4 3 9 6
9 7 9 10 4 3 9 6
9 10 9 7 4 3 9 6
4 7 4 10 4 3 9 6
4 10 4 7 4 3 9 6
0 6 3 6 4 3 9 6
3 6 0 6 4 3 9 6
1 3 3 3 4 3 9 6
3 3 1 3 4 3 9 6
4 0 4 2 4 3 9 6
4 2 4 0 4 3 9 6
5 3 8 5 4 3 9 6
8 5 5 3 4 3 9 6
5 3 8 3 4 3 9 6
8 3 5 3 4 3 9 6
6 4 6 5 4 3 9 6
6 5 6 4 4 3 9 6
4 3 9 6 4 3 9 6
9 6 4 3 4 3 9 6
4 3 5 4 4 3 9 6
5 4 4 3 4 3 9 6
5 3 8 3 4 3 9 6
8 3 5 3 4 3 9 6
5 3 9 3 4 3 9 6
9 3 5 3 4 3 9 6
4 4 4 5 4 3 9 6
4 5 4 4 4 3 9 6
4 3 4 5 4 3 9 6
4 5 4 3 4 3 9 6
4 3 4 6 4 3 9 6
4 6 4 3 4 3 9 6
9 2 9 5 4 3 9 6
9 5 9 2 4 3 9 6
9 2 9 7 4 3 9 6
9 7 9 2 4 3 9 6

?

out

?

F
F
F
T
T
F
T
F
F
F
T
T
F
T
F
F
F
T
T
F
T
F
F
F
T
T
F
T
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
T
T
T
T
T
T
T
T
T
T
T
T
T
T
T
T
T
T
T
T
T
T
T
T

???
???
??
??

poj 1410 Intersection 線段相交判斷