POJ 2653 Pick-up sticks （线段与线段相交）

题意：按顺序将n个棍子放在桌上，求在最上面的棍子是哪几根。

题解：线段与线段相交
暴力枚举当前棍子与之后放的棍子是否相交即可。

一开始声明变量为int了，研究半天还以为板子错了…

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<queue>
#include<stack>
#include<cmath>
#include<vector>
#include<fstream>
#include<set>
#include<map>
#include<sstream>
#include<iomanip>
#define ll long long
using namespace std;
const double eps = 1e-8;
const double inf = 1e20;
const double pi = acos(-1.0);
const int maxp = 1e5 + 5;
//Compares a double to zero
int sgn(double x) {
    if (fabs(x) < eps) return 0;
    if (x < 0) return -1;
    else return 1;
}

//POINT
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;
    }
};

//LINE
struct Line {
    Point s, e;
    Line() {}
    Line(Point _s, Point _e) {
        s = _s;
        e = _e;
    }
    //两线段相交判断
    //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 n;
double xa, ya, xb, yb;
Line l[maxp];
bool flag[maxp];
int main() {
	while (~scanf("%d", &n) && n) {
        memset(flag, true, sizeof(flag));
        for (int i = 1; i <= n; i++) {
            scanf("%lf%lf%lf%lf", &xa, &ya, &xb, &yb);
            l[i] = Line(Point(xa, ya), Point(xb, yb));
        }
        for (int i = 1; i <= n; i++) {
            for (int j = i + 1; j <= n; j++) {
                if (l[i].segcrossseg(l[j])) {
                    flag[i] = false;
                    break;
                }
            }
        }
        printf("Top sticks: ");
        bool first = true;
        for (int i = 1; i <= n; i++) {
            if (flag[i]) {
                if (first) first = false;
                else printf(", ");
                printf("%d", i);
            }
        }
        printf(".\n");
	}
	return 0;
}