線分の交点を判断する
1544 ワード
参考資料
http://www.cnblogs.com/zhangchaoyang/articles/2668562.html
コード
http://www.cnblogs.com/zhangchaoyang/articles/2668562.html
コード
#include
#include
using namespace std;
typedef struct node
{
int x;
int y;
} NODE;
int cross_products(NODE a,NODE b,NODE c)
{
int x1=b.x-a.x;
int y1=b.y-a.y;
int x2=c.x-a.x;
int y2=c.y-a.y;
return x1*y2-x2*y1;
}
bool on_segment(NODE a,NODE b,NODE c)
{
if((c.x>=a.x && c.x<=b.x || c.x>=b.x && c.x<=a.x) && (c.y>=a.y && c.y<=b.y || c.y>=b.y && c.y<=a.y))
return true;
return false;
}
bool segment_intersection(NODE p1,NODE p2,NODE p3,NODE p4)
{
int d1=cross_products(p3,p4,p1);
int d2=cross_products(p3,p4,p2);
int d3=cross_products(p1,p2,p3);
int d4=cross_products(p1,p2,p4);
if(d1*d2<0&& d3*d4<0)
return true;
else if(d1==0 && on_segment(p3,p4,p1))
return true;
else if(d2==0 && on_segment(p3,p4,p2))
return true;
else if(d3==0 && on_segment(p1,p2,p3))
return true;
else if(d4==0 && on_segment(p1,p2,p4))
return true;
return false;
}
int main()
{
NODE p[5];
while(1)
{
for(int i=1; i<=4; i++)
scanf("%d%d",&p[i].x,&p[i].y);
if(segment_intersection(p[1],p[2],p[3],p[4]))
printf("yes
");
else
printf("no
");
}
return 0;
}