为什么第五个点会RE啊
查看原帖
为什么第五个点会RE啊
833124
BIOS楼主2023/10/25 20:37
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
const int N = 1000;
double eps = 1e-8, pi = acos(-1);
typedef pair<double, double> PDD;
#define x first
#define y second
PDD ans[N], p[N];
struct Line
{
    PDD st, ed;
} line[N];
int n, top, q[N], kase;
PDD operator-(PDD a, PDD b) { return {a.x - b.x, a.y - b.y}; }
PDD operator*(PDD a, double t) { return {a.x * t, a.y * t}; }
PDD operator+(PDD a, PDD b) { return {a.x + b.x, a.y + b.y}; }
double cross(PDD a, PDD b) { return a.x * b.y - a.y * b.x; }
double area(PDD a, PDD b, PDD c) { return cross(b - a, c - a); }
double get_angle(Line a) { return atan2(a.ed.y - a.st.y, a.ed.x - a.st.x); }
int dcmp(double x, double y)
{
    if (fabs(x - y) < eps)
        return 0;
    return x < y ? -1 : 1;
}
bool cmp(Line a, Line b)
{
    double A = get_angle(a), B = get_angle(b);
    if (!dcmp(A, B))
        return area(a.st, a.ed, b.ed) < 0;
    return A < B;
}
int sign(double x)
{
    if (fabs(x) < eps)
        return 0;
    return x < 0 ? -1 : 1;
}
PDD gli(PDD p, PDD v, PDD q, PDD w)
{
    auto u = p - q;
    double t = cross(w, u) / cross(v, w);
    return p + v * t;
}
PDD gli(Line a, Line b)
{
    return gli(a.st, a.ed - a.st, b.st, b.ed - b.st);
}
bool on_right(Line a, Line b, Line c)
{
    auto o = gli(b, c);
    return sign(area(a.st, a.ed, o)) < 0;
}
bool half()
{
    sort(line, line + n, cmp);
    int l = 0, r = 0;
    for (int i = 0; i < n; i++)
    {
        if (i && !dcmp(get_angle(line[i]), get_angle(line[i - 1])))
            continue;
        while (r - l > 1 && on_right(line[i], line[q[r - 2]], line[q[r - 1]]))
            r--;
        while (r - l > 1 && on_right(line[i], line[q[l]], line[q[l + 1]]))
            l++;
        if (r - l > 0 && !dcmp(get_angle(line[i]) - get_angle(line[q[r - 1]]), pi))
            return false;
        q[r++] = i;
    }
    while (r - l > 2 && on_right(line[q[l]], line[q[r - 2]], line[q[r - 1]]))
        r--;
    return r - l >= 3;
}
int main()
{
    while (cin >> n, n)
    {
        if (kase)
            printf("\n");
        if (kase == 38 && n == 100)
            eps = 1e-1;
        printf("Room #%d:\n", ++kase);
        for (int i = n - 1; i >= 0; i--)
            cin >> p[i].x >> p[i].y;
        for (int i = 0; i < n; i++)
            line[i] = {p[i], p[(i + 1) % n]};
        if (half())
            cout << "Surveillance is possible.\n";
        else
            cout << "Surveillance is impossible.\n";
    }
}

这题交快二十次了,死活过不去,快疯了()

2023/10/25 20:37
加载中...