## poj1410巧妙变成直线与线段相交

2019年04月18日 算法 ⁄ 共 3038字 ⁄ 字号 评论关闭

这题粗看还以为是线段与线段相交，但是题目要求，线段完全在矩形内也是算相交。所以可以变成目标线段a所在的直线与矩形的各个线段相交问题，然后再看该线段a是否在矩形范围内。

```#include <iostream>
using namespace std;

struct Point
{
Point()
{
x=0.0f;
y=0.0f;
}

Point(double tx,double ty)
{
x=tx;
y=ty;
}

double x,y;
};

struct Segment
{
Point point1,point2;
};

double Min(double a,double b)
{
if(a<b)
return a;
else
return b;
}

double Max(double a,double b)
{
if(a<b)
return b;
else
return a;
}

double CrossProduct(Point vec1,Point vec2)
{
return (vec1.x*vec2.y)-(vec1.y*vec2.x);
}

//Calculate the crossproduct of (p2-p1)*(p3-p1)
double Direction(Point point1,Point point2,Point point3)
{
Point vec1;
vec1.x=point2.x-point1.x;
vec1.y=point2.y-point1.y;

Point vec2;
vec2.x=point3.x-point1.x;
vec2.y=point3.y-point1.y;

return CrossProduct(vec1,vec2);
}

//See if line interact the segment.
bool LineInteractSegment(Segment line,Segment seg)
{
Point vec1;
vec1.x=line.point2.x-line.point1.x;
vec1.y=line.point2.y-line.point2.y;

Point vec2;
vec2.x=seg.point2.x-seg.point1.x;
vec2.y=seg.point2.y-seg.point2.y;

double cross1=CrossProduct(
Point(line.point2.x-line.point1.x,line.point2.y-line.point1.y ),
Point(seg.point1.x-line.point1.x,seg.point1.y-line.point1.y));

double cross2=CrossProduct(
Point(line.point2.x-line.point1.x,line.point2.y-line.point1.y ),
Point(seg.point2.x-line.point1.x,seg.point2.y-line.point1.y));

if(cross1*cross2<=0)
return true;
else
return false;
}

bool SegmentInRect(Segment seg,Point leftTopPoint,Point rightBottomPoint )
{
double minX=Min(seg.point1.x,seg.point2.x);
double maxX=Max(seg.point1.x,seg.point2.x);

double minY=Min(seg.point1.y,seg.point2.y);
double maxY=Max(seg.point1.y,seg.point2.y);

if(minX>rightBottomPoint.x || maxX<leftTopPoint.x)
{
return false;
}
else
{
if(minY>leftTopPoint.y || maxY<rightBottomPoint.y)
{
return false;
}
else
{
return true;
}
}
}

void SwapData(double& a,double& b)
{
double c=a;
a=b;
b=c;
return;
}

int main()
{
bool HaveInteraction=false;
Segment seg;
Segment rectSeg[4];
double leftTopX,leftTopY,rightBottomX,rightBottomY;

int tCase;
//cin>>tCase;
scanf("%d",&tCase);
while(tCase>0)
{
tCase--;

//cin>>seg.point1.x>>seg.point1.y>>seg.point2.x>>seg.point2.y;
scanf("%lf%lf%lf%lf",&seg.point1.x,&seg.point1.y,&seg.point2.x,&seg.point2.y);

//cin>>leftTopX>>leftTopY>>rightBottomX>>rightBottomY;
scanf("%lf%lf%lf%lf",&leftTopX,&leftTopY,&rightBottomX,&rightBottomY);

if(leftTopX>rightBottomX)
SwapData(leftTopX,rightBottomX);
if(rightBottomY>leftTopY)
SwapData(rightBottomY,leftTopY);

//start from | ,take turn in clockwise.
rectSeg[0].point1= Point(leftTopX,rightBottomY);
rectSeg[0].point2= Point(leftTopX,leftTopY);

rectSeg[1].point1= Point(leftTopX,leftTopY);
rectSeg[1].point2= Point(rightBottomX,leftTopY);

rectSeg[2].point1= Point(rightBottomX,leftTopY);
rectSeg[2].point2= Point(rightBottomX,rightBottomY);

rectSeg[3].point1= Point(rightBottomX,rightBottomY);
rectSeg[3].point2= Point(leftTopX,rightBottomY);

HaveInteraction=false;
for(int i=0;i<4;i++)
{
if(LineInteractSegment(seg,rectSeg[i]))//the line interact with the rectangle, see if the segment interact the rectangle too.
{
if(SegmentInRect(seg, Point(leftTopX,leftTopY), Point(rightBottomX,rightBottomY)))
{
//cout<<"T"<<endl;
printf("T\n");
HaveInteraction=true;
}
break;
}
}

if(HaveInteraction==false)
{
//cout<<"F"<<endl;
printf("F\n");
}

}

return 0;
}```