欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

POJ 2653 Pick-up sticks (线段与线段相交)

程序员文章站 2022-06-03 19:34:10
...

题意:按顺序将n个棍子放在桌上,求在最上面的棍子是哪几根。
POJ 2653 Pick-up sticks (线段与线段相交)
题解:线段与线段相交
暴力枚举当前棍子与之后放的棍子是否相交即可。

一开始声明变量为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;
}