题意如题目
有几个点1.怪我没读好题目：给出的矩形两个端点不一定都是左上右下，但是肯定能勾勒出一个矩形。
2.现在才发现很多线段相交的判断我都没有仔细考虑这一个问题
bool ssinsert(Point p1,Point p2,Point p3,Point p4)
{ if(p1.x == p2.x && p3.x == p4.x && p2.x == p3.x)
{
if(max(p1.y,p2.y) < min(p3.y,p4.y) || min(p1.y,p2.y) > max(p3.y,p4.y))return false;
else return true;
}
if(p1.y == p2.y && p3.y == p4.y && p2.y == p3.y)
{
if(max(p1.x,p2.x) < min(p3.x,p4.x) || min(p1.x,p2.x) > max(p3.x,p4.x))return false;
else return true;
}
if(cross(p1,p2,p3) * cross(p1,p2,p4) < eps &&
cross(p3,p4,p1) * cross(p3,p4,p2) < eps)return true;
return false;
}
对于很多不需要严格线段相交的题目，也就是有一条线段的端点在另一条线段上，这样结果就是零，但是这样判断的共线是共直线如果两个线段的判定都平行于x轴但没有焦点，就会误判，所以前面我做了预处理
#include <iostream>
#include <vector>
#define eps 1e-10
using namespace std;
struct Point
{
double x,y;
Point (double x = 0.0,double y = 0.0):x(x),y(y){}
Point operator - (Point p){return Point(x - p.x,y - p.y);}
};
struct segment
{
Point p1,p2;
segment(Point p1 = Point(0.0,0.0),Point p2 = Point(0.0,0.0)):p1(p1),p2(p2){}
};
vector<segment> ls;
void init()
{
ls.clear();
}
double cross(Point p0,Point p1,Point p2)
{
Point a = p1 - p0;
Point b = p2 - p0;
return a.x * b.y - a.y * b.x;
}
bool ssinsert(Point p1,Point p2,Point p3,Point p4)
{ if(p1.x == p2.x && p3.x == p4.x && p2.x == p3.x)
{
if(max(p1.y,p2.y) < min(p3.y,p4.y) || min(p1.y,p2.y) > max(p3.y,p4.y))return false;
else return true;
}
if(p1.y == p2.y && p3.y == p4.y && p2.y == p3.y)
{
if(max(p1.x,p2.x) < min(p3.x,p4.x) || min(p1.x,p2.x) > max(p3.x,p4.x))return false;
else return true;
}
if(cross(p1,p2,p3) * cross(p1,p2,p4) < eps &&
cross(p3,p4,p1) * cross(p3,p4,p2) < eps)return true;
return false;
}
bool inner(Point p1,Point p2,Point p3,Point p4)
{
if(min(p1.y,p2.y) >= min(p3.y,p4.y) && max(p1.y,p2.y) <= max(p3.y,p4.y) &&
min(p1.x,p2.x) >= min(p3.x,p4.x) && max(p1.x,p2.x) <= max(p3.x,p4.x))return true;
return false;
}
int main()
{
int t;
double x1,y1,x2,y2;
scanf("%d",&t);
while(t--)
{
ls.clear();
scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
ls.push_back(segment(Point(x1,y1),Point(x2,y2)));
scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
double minx = min(x1,x2);
double maxx = max(x1,x2);
double miny = min(y1,y2);
double maxy = max(y1,y2);
Point a(minx,miny); Point b(minx,maxy);
Point c(maxx,maxy); Point d(maxx,miny);
//printf("a %lf %lf\n b %lf %lf\nc %lf %lf\nd %lf %lf\n",a.x,a.y,b.x,b.y,c.x,c.y,d.x,d.y);
ls.push_back(segment(a,b)); ls.push_back(segment(b,c));
ls.push_back(segment(c,d)); ls.push_back(segment(d,a));
int flag = 0;
for(int i = 1;i < ls.size();i++)
{
if(ssinsert(ls[0].p1,ls[0].p2,ls[i].p1,ls[i].p2) || inner(ls[0].p1,ls[0].p2,b,d))
{
flag = 1;
break;
}
}
if(flag)
{
printf("T\n");
}
else
{
printf("F\n");
} }
return 0;
}