计算几何的题目， 学cv的要做一下。poj 地址： http://poj.org/problem?id=1410
题意：判断一个直线段，是否与一个矩形有相交点。
解决方案： 判断矩形的每一条边是否与直线段相交， 则归结为判断直线段相交问题，然后判断两条线段是否相交的条件，是看每一条线段的两个点，是否分布在另一条直线的两端。 利用斜率可以求解。
// // 1410
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <cmath>
#include <vector>
using namespace std; struct Node{
double x,y;
}; int Orientation(Node& a, Node& b, Node& c){
double val = (a.y- b.y)*(b.x-c.x) - (a.x-b.x)*(b.y-c.y);
if(fabs(val -0) < 1e-8){
return 0;
}else if(val > 0){
return 1;
}else{
return -1;
}
} bool onScope(Node& a, Node& b, Node& c){
if(c.x <=max(a.x, b.x) && c.x >=min(a.x, b.x) \
&& c.y <=max(a.y, b.y) && c.y >= min(a.y, b.y)){
return true;
}else{
return false;
}
} bool LineIntersect(Node& a, Node& b, Node& c, Node& d){
int val1 = Orientation(a, b, c);
int val2 = Orientation(a, b, d);
int val3 = Orientation(c, d, a);
int val4 = Orientation(c, d, b);
if( val1 != val2 && val3 != val4){
return true;
}
if(val1 == 0 && onScope(a, b, c)){ return true; }
if(val2 == 0 && onScope(a, b, d)){ return true; }
if(val3 == 0 && onScope(c, d, a)){ return true; }
if(val4 == 0 && onScope(c, d, b)){ return true; }
return false;
} int main(){
freopen("in.txt", "r", stdin); int test_num;
Node start, end, lt, rb;
bool flag;
scanf("%d", &test_num);
while(test_num--){
scanf("%lf %lf %lf %lf", &start.x, &start.y, &end.x, &end.y);
scanf("%lf %lf %lf %lf", <.x, <.y, &rb.x, &rb.y);
Node rt, lb;
rt.x = rb.x; rt.y = lt.y;
lb.x = lt.x; lb.y = rb.y;
if(LineIntersect(start, end, lt, rt) || LineIntersect(start, end, rt, rb) \
|| LineIntersect(start, end, rb, lb) || LineIntersect(start, end, lb, lt)){
printf("T\n");
}else{
if(min(start.x, end.x)>min(lt.x, rb.x) && max(start.x, end.x)<max(lt.x, rb.x) \
&& min(start.y, end.y)>min(lt.y, rb.y) && max(start.y, end.y)<max(lt.y, rb.y)){
printf("T\n");
}else{
printf("F\n");
}
}
}
return 0;
}
reference: http://www.geeksforgeeks.org/check-if-two-given-line-segments-intersect/