THUPC2021-非欧几何 题解

写在前面

首先是咱的Blog....因为一直以来的懒和不整修，在一位"好"朋友的帮助下...
咱原来部署在香港的服务成功宕机并且被锁定...无法申诉(x

所以目前的Blog的文章都失去了备份...咱只能重写并认识到了备份的重要性.jpg

在某只鸽子的邀请(×)胁迫(√)下，咱姑且看了几道他比较喜欢的THUPC2021的选题
也和他讨论这道题讨论了很久，故有了今天这份Write up

THUPC2021初赛-非欧几何

题目大意

欧几里德几何和非欧几里德几何
传统派vs维新派
路人怎么也被卷入进来了(吐槽)

Tinytree和ustze分别在一个球面上确定了一些圆，然后Kiana想知道一些点是否在安全区域、危险区域或者中间区域，球面的半径和点的坐标都给定，需要判断这些点的位置关系，和是否方便卡其脱离太

原题Link：https://www.luogu.com.cn/problem/P7138

思路

某只鸽子的思路大概是在球面上通过点与北极点的连线来描述平面，然后把平面映射到二维平面上再分析平面和球的关系

而咱构思的思路的话...类似于直接计算点到给定圆的距离来判断它们的位置关系
这样就不用把平面映射到二维平面上
但是要算三维坐标，如果实在是懒得不行的话...也可以学他直接映射下去算UV(

Code

#include <bits/stdc++.h>
#include <immintrin.h>
using namespace std;

#define gc (c = getchar())

template <typename T>
void chmin(T &x, const T &y) {
    if (x > y)
        x = y;
}

template <typename T>
void chmax(T &x, const T &y) {
    if (x < y)
        x = y;
}

typedef int64_t s64;
typedef uint64_t u64;
typedef uint32_t u32;
typedef pair<int, int> pii;

#define rep(i, l, r) for (int i = l; i <= r; ++i)
#define per(i, r, l) for (int i = r; i >= l; --i)
#define rep0(i, l, r) for (int i = l; i < r; ++i)

char readc() {
    char c;

    while (isspace(gc));

    return c;
}

int read() {
    char c;

    while (gc < '-');

    if (c == '-') {
        int x = gc - '0';

        while (gc >= '0')
            x = x * 10 + c - '0';

        return -x;
    }

    int x = c - '0';

    while (gc >= '0')
        x = x * 10 + c - '0';

    return x;
}

#undef gc

double sqr(const double &x) {
    return x * x;
}

int sgn(const double &x, const double &eps = 1e-9) {
    return x < -eps ? -1 : x > eps;
}

struct Point {
    double x, y;
};

Point operator +(const Point &a, const Point &b) {
    return {a.x + b.x, a.y + b.y};
}

Point operator -(const Point &a, const Point &b) {
    return {a.x - b.x, a.y - b.y};
}

double operator *(const Point &a, const Point &b) {
    return a.x * b.y - a.y * b.x;
}

Point operator *(const Point &a, const double &b) {
    return {a.x * b, a.y * b};
}

struct Line {
    Point p, v;
    double a;

    void calc() {
        a = atan2(v.y, v.x);
    }
};

bool left(const Point &p, const Line &l) {
    return l.v * (p - l.p) > 0;
}

Point pos(const Line &a, const Line &b) {
    double t = ((b.p - a.p) * b.v) / (a.v * b.v);
    return a.p + a.v * t;
}

const int N = 5000 + 10;

struct HalfPlanes {
    Point p[N], p1[N], p2[N];
    Line line[N], q[N];
    int cnt_line, n1, n2;

    void newLine(Point a, Point b) {
        if (sgn((b - a) * a) > 0)
            swap(a, b);

        line[++cnt_line] = {a, b - a};
    }

    void build() {
        rep(i, 1, cnt_line) line[i].calc();

        sort(line + 1, line + cnt_line + 1, [&](const Line &a, const Line &b) {
            return a.a < b.a;
        });

        int h = 1, t = 1;
        q[1] = line[1];

        rep(i, 2, cnt_line) {
            while (h < t && !left(p[t - 1], line[i]))
                --t;

            while (h < t && !left(p[h], line[i]))
                ++h;

            if (sgn(q[t].a - line[i].a) == 0)
                q[t] = left(q[t].p, line[i]) ? q[t] : line[i];
            else
                q[++t] = line[i];

            if (h < t)
                p[t - 1] = pos(q[t], q[t - 1]);
        }

        while (h < t && !left(p[t - 1], q[h]))
            --t;

        p[t] = pos(q[t], q[h]);

        if (t - h <= 1)
            return;

        int mn = h;

        rep(i, h, t)
        if (p[i].x < p[mn].x)
            mn = i;

        rotate(p + h, p + mn, p + t + 1);
        int m = h;

        while (m < t && p[m + 1].x >= p[m].x)
            ++m;

        rep(i, h, m) p1[++n1] = p[i];
        p2[++n2] = p[h];
        per(i, t, m) p2[++n2] = p[i];
        rep(i, 1, n2) p2[i].y *= -1;
    }

    bool check(Point p1[], int n1, Point p) {
        if (sgn(p.x - p1[1].x) < 0 || sgn(p.x - p1[n1].x) > 0)
            return 0;

        p.x += 1e-9;
        Point *i = lower_bound(p1 + 1, p1 + n1, p, [&](const Point &a, const Point &b) {
            return a.x < b.x;
        });
        p.x -= 1e-9;
        --i;
        return (*(i + 1) - *i) * (p - *i) > 0;
    }

    bool contain(const Point &p) {
        return n1 && check(p1, n1, p) && check(p2, n2, {p.x, -p.y});
    }
} halfPlanes[2];

int main() {
#ifdef kcz
    freopen("1.in", "r", stdin); 
    #endif

    int n[2], t;
    cin >> n[0] >> n[1] >> t;
    int R;
    cin >> R;

    auto read_point = [&]() -> Point {
        double x, y;
        scanf("%lf%lf", &x, &y);
        x /= R;
        y /= R;
        double z = sqrt(1 - sqr(x) - sqr(y));

        if (readc() == '-')
            z = -z;

        ++z;
        return {2 * x / (2 - z), 2 * y / (2 - z)};
    };

    rep(j, 0, 1) {
        rep(i, 1, n[j]) {
            Point a = read_point(), b = read_point();
            halfPlanes[j].newLine(a, b);
        }

        static const double U = 1e9;
        halfPlanes[j].newLine({-U, -U}, {U, -U});
        halfPlanes[j].newLine({U, -U}, {U, U});
        halfPlanes[j].newLine({U, U}, {-U, U});
        halfPlanes[j].newLine({-U, U}, {-U, -U});
        halfPlanes[j].build();
    }

    while (t--) {
        Point p = read_point();

        if (!halfPlanes[0].contain(p))
            puts("Safe");
        else if (!halfPlanes[1].contain(p))
            puts("Goodbye");
        else
            puts("Passer");
    }
}