NEFU 922 判断线段相交

0
0
0
1. 云栖社区>
2. 博客>
3. 正文

## NEFU 922 判断线段相交

angel_imp 2015-06-09 20:19:00 浏览703

http://acm.nefu.edu.cn/JudgeOnline/problemshow.php?problem_id=922

``````#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
using namespace std;
typedef struct
{
int x,y;
}sa;
int chaji(sa a,sa b,sa c)//计算ca和cb
{
return (a.x-c.x)*(b.y-c.y)-(b.x-c.x)*(a.y-c.y);
}
bool online(sa a,sa b,sa c) //判断点c是否在线段ab上
{
if(min(a.x,b.x)<=c.x&&c.x<=max(a.x,b.x))
{
if(min(a.y,b.y)<=c.y&&c.y<=max(a.y,b.y))
{
return 1;
}
}
return 0;
}
bool xj(sa a,sa b,sa c,sa d)
{
int d2=chaji(c,d,b);//bc,bd
int d3=chaji(a,b,c);//ca,cb
int d4=chaji(a,b,d);//db,da
if(d1*d2<0&&d3*d4<0)
return 1;
else if(d1==0&&online(c,d,a))
return 1;
else if(d2==0&&online(c,d,b))
return 1;
else if(d3==0&&online(a,b,c))
return 1;
else if(d4==0&&online(a,b,d))
return 1;
return 0;
}
int main()
{
sa data[5];
int m;
while(cin>>m&&m)
{
while(m--)
{
for(int i=0;i<4;i++)
cin>>data[i].x>>data[i].y;
if(xj(data[0],data[1],data[2],data[3]))
cout<<"YES"<<endl;
else
cout<<"no"<<endl;
}
}
return 0;
}``````

angel_imp
+ 关注