HDU 1147 /// 判断两线段相交

题目大意：

给定n条线段的端点

依次放上n条线段 判断最后在最上面（不被覆盖）的线段有哪些

到当前线段后 直接与之前保存的未被覆盖的线段判断是否相交就可以了

#include <cstdio>
#include <algorithm>
#include <string.h>
#include <set>
#include <cmath>
#define INF 0x3f3f3f3f
using namespace std;

const double eps=1e-10;
double add(double a,double b) {
    if(abs(a+b)<eps*(abs(a)+abs(b))) return 0;
    return a+b;
}
struct P {
    double x,y;
    P(){};
    P(double _x,double _y):x(_x),y(_y){}
    P operator - (P p) { return P(add(x,-p.x),add(y,-p.y)); }
    P operator + (P p) { return P(add(x,p.x),add(y,p.y)); }
    P operator * (double d) { return P(x*d,y*d); }
    bool operator == (P p) { return x==p.x && y==p.y; }
    bool operator < (P p) {
        if(x==p.x) return y<p.y;
        return x<p.x;
    }
    double dot(P p) { return add(x*p.x,y*p.y); }
    double det(P p) { return add(x*p.y,-y*p.x); }
}p[200005];
int n;
set <int> s;
bool vis[100005];

P ins(P a,P b,P c,P d) {
    return a+(b-a)*((c-d).det(d-a)/(c-d).det(b-a));
}
bool onSeg(P a,P b,P c) {
    return (a-c).det(b-c)==0 && (a-c).dot(b-c)<=0;
}
bool insSS(P a,P b,P c,P d)
{
    if((a-b).det(c-d)==0) {
        return onSeg(a,b,c) || onSeg(a,b,d)
            || onSeg(c,d,a) || onSeg(c,d,b);
    }
    else {
        P r=ins(a,b,c,d);
        return onSeg(a,b,r) && onSeg(c,d,r);
    }
}

int main()
{
    while(~scanf("%d",&n)) {
        if(n==0) break;
        memset(vis,0,sizeof(vis));
        for(int i=1;i<=n;i++)
            scanf("%lf%lf%lf%lf",&p[i].x,&p[i].y,&p[i+n].x,&p[i+n].y);
        for(int i=1;i<=n;i++) 
            for(int j=i+1;j<=n;j++)
                if(insSS(p[i],p[i+n],p[j],p[j+n])) {
                    vis[i]=1; break;
                }
        bool yes=0;
        printf("Top sticks:");
        for(int i=1;i<=n;i++) {
            if(vis[i]) continue;
            if(yes) printf(", %d",i);
            else yes=1, printf(" %d",i);
        }
        printf(".
");
    }

    return 0;
}

这篇的注释里有直线交点的推导