ZOJ 1648 Circuit Board(线段相交判定)

ZOJ 1648 Circuit Board(线段相交判定)

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1648

题意:

给你二维平面的n个线段的端点坐标,问你这n条线段中是否存在任何两条线段相交?(就算两线段有交点,该交点也不可能出现在任何线段的端点处,即规范相交)

分析:

题意已经很明确了,要我们判断是否有线段存在规范相交的情况.

直接用刘汝佳<<训练指南>>的模板解决即可,这里不多说了.不明白的同学可以先去看看<<训练指南>>哦.

AC代码:

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const double eps=1e-10;

int dcmp(double x)
{
    if(fabs(x)<eps) return 0;
    return x<0?-1:1;
}

struct Point
{
    double x,y;
    Point(){}
    Point(double x,double y):x(x),y(y){}
};

typedef Point Vector;

Vector operator+(Vector A,Vector B)
{
    return Vector(A.x+B.x,A.y+B.y);
}
Vector operator-(Point A,Point B)
{
    return Vector(A.x-B.x,A.y-B.y);
}
Vector operator*(Point A,double p)
{
    return Vector(A.x*p, A.y*p);
}
Vector operator/(Point A,double p)
{
    return Vector(A.x/p,A.y/p);
}
double Cross(Vector A,Vector B)
{
    return A.x*B.y-A.y*B.x;
}
bool SegmentProperIntersection(Point a1,Point a2,Point b1,Point b2)
{
    double c1=Cross(a2-a1,b1-a1),c2=Cross(a2-a1,b2-a1);
    double c3=Cross(b2-b1,a1-b1),c4=Cross(b2-b1,a2-b1);
    return dcmp(c1)*dcmp(c2)<0 && dcmp(c3)*dcmp(c4)<0;
}
/***以上为刘汝佳模板***/






const int maxn=2000+5;
Point P[maxn],Q[maxn];//分别表示第i条线段的两个端点
int main()
{
    int n;
    while(scanf("%d",&n)==1)
    {
        for(int i=1;i<=n;++i) scanf("%lf%lf%lf%lf",&P[i].x,&P[i].y,&Q[i].x,&Q[i].y);
        bool ok=true;
        for(int i=1;i<=n;++i)
        for(int j=i+1;j<=n;++j)
        if(SegmentProperIntersection(P[i],Q[i],P[j],Q[j]))
        {
            ok=false;
            break;
        }
        printf("%s\n",ok?"ok!":"burned!");
    }
    return 0;
}