51nod 1264 线段相交（计算几何）

#include <iostream> #include <cstdio> #include <algorithm> #include <cmath> using namespace std; /* 计算几何 输入两条线段的四个端点，判断两直线是否相交 */ const double esp=1e-7; int sgn(double x) { if(fabs(x)<esp) return 0; if(x<0) return -1; else return 1; } struct Point { double x,y; Point() {} Point(double _x,double _y) { x=_x; y=_y; } Point operator -(const Point &b) const { return Point(x-b.x,y-b.y); } double operator ^ (const Point &b) const//叉积 { return x*b.y-y*b.x; } double operator * (const Point &b) const//点积 { return x*b.x+y*b.y; } double distance(Point p)//两点距离 { return hypot(x-p.x,y-p.y); //return (x-p.x)*(x-p.x)+(y-p.y)*(y-p.y); } }; struct Line { Point s,e; Line(){} Line(Point _s,Point _e) { s=_s; e=_e; } double length()//线段长度 { return s.distance(e); } double dispointtoline(Point p)//点到直线距离 { return fabs((p-s)^(e-s))/length(); } double dispointtoseg(Point p)//点到线段距离 { if(sgn((p-s)*(e-s))<0||sgn((p-e)*(s-e))<0) return min(p.distance(s),p.distance(e)); return dispointtoline(p); } //两线段相交判断 //2 规范相交 1 非规范相交 0 不相交 int segcrossseg(Line v) { int d1=sgn((e-s)^(v.s-s)); int d2=sgn((e-s)^(v.e-s)); int d3=sgn((v.e-v.s)^(s-v.s)); int d4=sgn((v.e-v.s)^(e-v.s)); if((d1^d2)==-2&&(d3^d4)==-2) return 2; return (d1==0&&sgn((v.s-s)*(v.s-e))<=0) ||(d2==0&&sgn((v.e-s)*(v.e-e))<=0) ||(d3==0&&sgn((s-v.s)*(s-v.e))<=0) ||(d4==0&&sgn((e-v.s)*(e-v.e))<=0); } }; int main() { int t; scanf("%d",&t); while(t--) { Point point[4]; for(int i=0;i<4;i++) { scanf("%lf%lf",&point[i].x,&point[i].y); } Line line[2]; line[0]=Line(point[0],point[1]); line[1]=Line(point[2],point[3]); int flag=line[0].segcrossseg(line[1]); if(flag) { printf("Yes\n"); } else { printf("No\n"); } } return 0; }