QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#482030#5067. Two Wallssunyuheng365WA 0ms3744kbC++1411.2kb2024-07-17 16:54:402024-07-17 16:54:41

Judging History

你现在查看的是最新测评结果

  • [2024-07-17 16:54:41]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3744kb
  • [2024-07-17 16:54:40]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define endl '\n'

const int N = 5e3 + 5;
using point_t = __int128_t;
constexpr point_t eps = 0;
constexpr long double PI = 3.1415926535897932384L;

__int128_t abs(__int128_t x) { return x < 0 ? -x : x; }

template <typename T>
struct point // 既是点, 也可以表示向量
{
    T x, y;
    bool operator==(const point &a) const { return (abs(x - a.x) <= eps && abs(y - a.y) <= eps); }
    bool operator<(const point &a) const
    {
        if (abs(x - a.x) <= eps)
            return y < a.y - eps;
        return x < a.x - eps;
    }
    bool operator>(const point &a) const { return !(*this < a || *this == a); }
    point operator+(const point &a) const { return {x + a.x, y + a.y}; }
    point operator-(const point &a) const { return {x - a.x, y - a.y}; }
    point operator-() const { return {-x, -y}; }
    point operator*(const T k) const { return {x * k, y * k}; }
    point operator/(const T k) const { return {x / k, y / k}; }
    // 点积
    T operator*(const point &a) const { return x * a.x + y * a.y; }
    // 叉积, 注意优先级
    T operator^(const point &a) const { return x * a.y - y * a.x; }
    // 判断向量 a 在当前向量哪一侧 (1:左侧 / 0:平行 / -1:右侧)
    int toleft(const point &a) const
    {
        const auto t = (*this) ^ a;
        return (t > eps) - (t < -eps);
    }
    // 向量长度的平方
    T len2() const { return (*this) * (*this); }
    // 两点距离的平方
    T dis2(const point &a) const { return (a - (*this)).len2(); }

    // 浮点数部分
    // 向量长度
    long double len() const { return sqrtl(len2()); }
    // 两点距离
    long double dis(const point &a) const { return sqrtl(dis2(a)); }
    // 向量夹角
    long double ang(const point &a) const { return acosl(max(-1.L, min(1.L, ((*this) * a) / (len() * a.len())))); }
    // 逆时针旋转指定角度
    point rot(const long double rad) const { return {x * cos(rad) - y * sin(rad), x * sin(rad) + y * cos(rad)}; }
    // 给定余弦值正弦值逆时针旋转
    point rot(const long double cosr, const long double sinr) const { return {x * cosr - y * sinr, x * sinr + y * cosr}; }
    int quad() const
    {
        if (y < -eps) // 下平面(三四象限, 包含 y 轴负半轴)
            return 1;
        if (y > eps) // 上平面(一二象限, 包含 y 轴正半轴)
            return 4;
        if (x < -eps) // x 轴负半轴
            return 5;
        if (x > eps) // x 轴正半轴
            return 3;
        return 2; // 原点
    };
};

using Point = point<point_t>;

// 极角排序
struct argcmp
{
    bool operator()(const Point &a, const Point &b) const
    {
        // 判断象限
        const auto quad = [](const Point &a)
        {
            if (a.y < -eps) // 下平面(三四象限, 包含 y 轴负半轴)
                return 1;
            if (a.y > eps) // 上平面(一二象限, 包含 y 轴正半轴)
                return 4;
            if (a.x < -eps) // x 轴负半轴
                return 5;
            if (a.x > eps) // x 轴正半轴
                return 3;
            return 2; // 原点
        };
        const int qa = quad(a), qb = quad(b);
        if (qa != qb) // 象限不同直接判
            return qa < qb;
        const auto t = a ^ b; // 判断向量 b 是否在向量 a 的左侧, 等同 a.toleft(b)
        // if (abs(t) <= eps) // 分离不同长度向量
        //     return a * a < b * b - eps;
        return t > eps;
    }
    // bool operator()(const Point &a, const Point &b) const
    // {
    //     // atan2 不带脑子丢精度方法
    //     return atan2l(a.y, a.x) < atan2l(b.y, b.x);
    // }
};

template <typename T>
struct line // 直线
{
    point<T> p, v; // p 为直线上一点 , v 为方向向量

    // 同一条直线 -- 方向向量平行且一条直线上一点在另一直线上
    bool operator==(const line &a) const { return v.toleft(a.v) == 0 && v.toleft(p - a.p) == 0; }
    // 检测点在直线的哪一侧 (1:左侧 / 0:在直线上 / -1:右侧)
    int toleft(const point<T> &a) const { return v.toleft(a - p); }

    // 半平面交排序
    bool operator<(const line &a)
    {
        if (abs(v ^ a.v) <= eps && v * a.v >= -eps)
            return toleft(a.p) == -1;
        return argcmp()(v, a.v);
    }

    // 浮点数部分
    // 直线交点
    point<T> inter(const line &a) const
    {
        return p + v * ((a.v ^ (p - a.p)) / (v ^ a.v));
    }
    // 点到直线距离
    long double dis(const point<T> &a) const { return abs(v ^ (a - p)) / v.len(); }
    // 点在直线上投影
    point<T> proj(const point<T> &a) const { return p + v * ((v * (a - p)) / (v * v)); }
};

using Line = line<point_t>;

template <typename T>
struct segment // 线段
{
    point<T> a, b; // 线段端点

    bool operator<(const segment &s) const { return make_pair(a, b) < make_pair(s.a, s.b); }

    // 判断性函数建议在整数域使用

    // 判断点是否在线段上
    // -1:点在线段端点 | 0:点不在线段上 | 1:点严格在线段上, 叉积用浮点数时精度注意有问题, 两个 10^9 级别叉积极大概率炸掉 10^(-9) 的 eps
    int is_on(const point<T> &p) const
    {
        if (p == a || p == b)
            return -1;
        // 点严格在线段上 = 向量 AP 与向量 BP 平行 且 异向
        return (p - a).toleft(p - b) == 0 && (p - a) * (p - b) < -eps;
    }

    // 判断线段和直线相交
    // -1:直线过线段端点 | 0:不相交 | 1:严格相交
    int is_inter(const line<T> &l) const
    {
        if (l.toleft(a) == 0 || l.toleft(b) == 0)
            return -1;
        return l.toleft(a) * l.toleft(b) == -1;
    }

    // 判断两线段相交
    // -1:在某一线段端点相交 | 0:不相交 | 1:严格相交
    int is_inter(const segment<T> &s) const
    {
        if (is_on(s.a) || is_on(s.b) || s.is_on(a) || s.is_on(b))
            return -1;
        // 转化为两条直线 格式:(端点,向量)
        const line<T> l{a, b - a}, ls{s.a, s.b - s.a};
        // 一条线段的两个端点总是在另一条线段所代表直线的异侧
        return l.toleft(s.a) * l.toleft(s.b) == -1 && ls.toleft(a) * ls.toleft(b) == -1;
    }

    // 点到线段距离
    long double dis(const point<T> &p) const
    {
        // 角 PAB 或 角 PBA > 90 度
        if ((p - a) * (b - a) < -eps || (p - b) * (a - b) < -eps)
            return min(p.dis(a), p.dis(b));
        const line<T> l{a, b - a};
        return l.dis(p);
    }

    // 两线段距离
    long double dis(const segment<T> &s) const
    {
        // 相交
        if (is_inter(s))
            return 0;
        return min({dis(s.a), dis(s.b), s.dis(a), s.dis(b)});
    }
};

using Segment = segment<point_t>;

// 多边形
template <typename T>
struct polygon
{
    vector<point<T>> p; // 逆时针存储

    int nxt(const int i) const { return i == (int)p.size() - 1 ? 0 : i + 1; }
    int pre(const int i) const { return i == 0 ? (int)p.size() - 1 : i - 1; }

    // 回转数
    // 返回值第一项表示点是否在多边形上
    // 对于狭义多边形, 回转数为 0 表示点在多边形外, 否则点在多边形内
    pair<bool, int> winding(const point<T> &a) const
    {
        // 这里我们引出射线方向为 x 轴正方向
        int cnt = 0;
        for (int i = 0; i < (int)p.size(); i++)
        {
            const point<T> u = p[i], v = p[nxt(i)];
            // 叉积判断点 a 是否在直线 uv 上, 点积判断点 a 是否和某个端点重合或 u, v 两点在点 a 异侧
            if (abs((a - u) ^ (a - v)) <= eps && (a - u) * (a - v) <= eps)
                return {true, 0};
            // 该线段和 x 轴平行, 向上浮动后视作无交点
            if (abs(u.y - v.y) <= eps)
                continue;
            const Line uv = {u, v - u};
            // 指向北方, 点在其右侧, 视作无交点
            if (u.y < v.y - eps && uv.toleft(a) <= 0)
                continue;
            // 指向南方, 点在其左侧, 视作无交点
            if (u.y > v.y + eps && uv.toleft(a) >= 0)
                continue;
            // (u.y < v.y) 指向北方, 点在其左侧, 且点的纵坐标位于指定 Range
            if (u.y < a.y - eps && v.y >= a.y - eps)
                cnt++;
            // (u.y > v.y) 指向南方, 点在其右侧, 且点的纵坐标位于指定 Range
            if (u.y >= a.y - eps && v.y < a.y - eps)
                cnt--;
        }
        return {false, cnt};
    }
    T area() const
    {
        T sum = 0;
        for (int i = 0; i < (int)p.size(); i++)
            sum += p[i] ^ p[nxt(i)];
        return sum;
    }
    long double circ() const
    {
        long double sum = 0;
        for (int i = 0; i < (int)p.size(); i++)
            sum += p[i].dis(p[nxt(i)]);
        return sum;
    }
};
using Polygon = polygon<point_t>;

int n;
Point a[N];

void solve()
{
    Point A, B, C, D, E, F;

    int a[12];
    for (int i = 0; i < 12; i++)
        cin >> a[i];

    A.x = a[0], A.y = a[1];
    B.x = a[2], B.y = a[3];
    C.x = a[4], C.y = a[5], D.x = a[6], D.y = a[7];
    E.x = a[8], E.y = a[9], F.x = a[10], F.y = a[11];

    Segment AB{A, B}, CD{C, D}, EF{E, F};
    if (AB.is_inter(CD) == 0 && AB.is_inter(EF) == 0)
        return std::cout << 0 << endl, void();

    if (C == D || E == F || CD.is_inter(EF) != 1 ||
        Line{C, D - C}.toleft(A) == 0 ||
        Line{C, D - C}.toleft(B) == 0 ||
        Line{E, F - E}.toleft(A) == 0 ||
        Line{E, F - E}.toleft(B) == 0) // 退化
        return std::cout << 1 << endl, void();

    for (Point u : {C, D, E, F})
        for (Point v : {C, D, E, F})
        {
            // A -> u
            // B -> v
            Line AU{A, u - A}, BV{B, v - B};
            if (!(AU == BV) && (AU.v ^ BV.v) == 0)
                continue;
            auto judge = [&](Segment x, Line y)
            {
                if (x.is_inter(y) && (x.is_on(y.p) || x.is_on(y.p + y.v) ||                                         // 射线和线段有交点
                                      Line{x.a, x.b - x.a}.toleft(y.p) != Line{x.a, x.b - x.a}.toleft(y.p + y.v) || // 射线上有两点在线段异侧
                                      abs((x.b - x.a) ^ (y.p - x.a)) > abs((x.b - x.a) ^ (y.p + y.v - x.a))))       // 射线上在线段同侧的两点围成的三角形面积变化
                {
                    if (x.is_on(u) && y.toleft(u) == 0) // 交点是 u
                        return true;
                    if (x.is_on(v) && y.toleft(v) == 0) // 交点是 v
                        return true;
                    return false;
                }
                return true;
            };
            if (judge(CD, AU) && judge(CD, BV) && judge(EF, AU) && judge(EF, BV))
                return std::cout << 1 << endl, void();
        }

    std::cout << 2 << endl, void();
}

signed main()
{
#ifndef sunyuheng365
    ios::sync_with_stdio(false);
#endif
    int tc = 1;
    cin >> tc;
    while (tc--)
        solve();
#ifdef sunyuheng365
    system("pause");
#endif
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3744kb

input:

3
0 0
1 1
2 2 3 3
4 4 5 5
0 0
1 1
2 2 3 3
2 2 3 3
0 0
10 10
10 0 0 10
1 1 2 2

output:

0
0
1

result:

ok 3 number(s): "0 0 1"

Test #2:

score: -100
Wrong Answer
time: 0ms
memory: 3744kb

input:

2
-999999999 999999998
999999999 999999998
-1000000000 -1000000000 1000000000 1000000000
1000000000 -1000000000 -1000000000 1000000000
-999999999 999999998
999999999 999999998
-999999998 -999999998 1000000000 1000000000
999999998 -999999998 -1000000000 1000000000

output:

1
1

result:

wrong answer 1st numbers differ - expected: '2', found: '1'