Untitled

 avatar
unknown
c_cpp
a year ago
6.3 kB
11
Indexable
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
#define all(x) (x).begin(), (x).end()

#define endl '\n'
#define int ll

namespace Geometry {

using T = long double;
const T EPS = 0;
const double PI = acos(-1.0);

template <typename T, typename V>
int cmp(T a, V b) {
    return (a -= b) < -EPS ? -1 : (a > EPS ? 1 : 0);
}
template <typename T, typename V>
bool iseq(T a, V b) {
    return cmp(a, b) == 0;
}
template <typename T>
bool iseq0(T a) {
    return cmp(a, 0) == 0;
}
template <typename T, typename V>
bool islte(T a, V b) {
    return cmp(a, b) != 1;
}
template <typename T, typename V>
bool isgte(T a, V b) {
    return cmp(a, b) != -1;
}
template <typename T, typename V>
bool islt(T a, V b) {
    return cmp(a, b) == -1;
}
template <typename T, typename V>
bool isgt(T a, V b) {
    return cmp(a, b) == 1;
}
template <typename T>
int sign(T val) {
    return cmp(val, 0);
}

enum PointState { OUT, IN, ON };

typedef struct Point {
    T x, y;

    Point() {}
    Point(T _x, T _y) : x(_x), y(_y) {}
    Point operator+(const Point &p) const { return Point(x + p.x, y + p.y); }
    Point operator-(const Point &p) const { return Point(x - p.x, y - p.y); }
    Point operator/(T denom) const { return Point(x / denom, y / denom); }
    Point operator*(T scaler) const { return Point(x * scaler, y * scaler); }

    T dot(const Point &p) const { return x * p.x + y * p.y; }
    T cross(const Point &p) const { return x * p.y - y * p.x; }
    T dot(const Point &a, const Point &b) const {
        return (a - *this).dot(b - *this);
    }
    T cross(const Point &a, const Point &b) const {
        return (a - *this).cross(b - *this);
    }
    T norm() const { return dot(*this); }

    long double len() const { return sqrtl(dot(*this)); }
    long double ang(bool pos = true) const {
        auto a = atan2l(y, x);
        if (pos && a < 0) a += PI * 2;
        return a;
    }

    Point rotate(const Point &p, long double a) {
        return (*this - p).rotate(a) + p;
    }

    Point rotate(long double angle) {
        auto l = len(), a = ang();
        return Point(l * cosl(a + angle), l * sinl(a + angle));
    }

    bool operator==(const Point &p) const { return (*this - p).norm() <= EPS; }
    bool operator!=(const Point &p) const { return !(*this == p); }
    bool operator<(const Point &p) const {
        return x < p.x || (x == p.x && y < p.y);
    }
    friend ostream &operator<<(ostream &os, const Point &p) {
        return os << '(' << p.x << ',' << p.y << ')';
    }
    friend istream &operator>>(istream &is, Point &p) {
        return is >> p.x >> p.y;
    }
} pt;

typedef struct Pointll {
    typedef long long T;
    T x, y;

    Pointll() {}
    Pointll(T _x, T _y) : x(_x), y(_y) {}
    Pointll operator+(const Pointll &p) const { return Pointll(x + p.x, y + p.y); }
    Pointll operator-(const Pointll &p) const { return Pointll(x - p.x, y - p.y); }
    Pointll operator/(T denom) const { return Pointll(x / denom, y / denom); }
    Pointll operator*(T scaler) const { return Pointll(x * scaler, y * scaler); }

    T dot(const Pointll &p) const { return x * p.x + y * p.y; }
    T cross(const Pointll &p) const { return x * p.y - y * p.x; }
    T dot(const Pointll &a, const Pointll &b) const {
        return (a - *this).dot(b - *this);
    }
    T cross(const Pointll &a, const Pointll &b) const {
        return (a - *this).cross(b - *this);
    }
    T norm() const { return dot(*this); }

    long double len() const { return sqrtl(dot(*this)); }
    long double ang(bool pos = true) const {
        auto a = atan2l(y, x);
        if (pos && a < 0) a += PI * 2;
        return a;
    }

    Pointll rotate(const Pointll &p, long double a) {
        return (*this - p).rotate(a) + p;
    }

    Pointll rotate(long double angle) {
        auto l = len(), a = ang();
        return Pointll(l * cosl(a + angle), l * sinl(a + angle));
    }

    bool operator==(const Pointll &p) const { return (*this - p).norm() <= EPS; }
    bool operator!=(const Pointll &p) const { return !(*this == p); }
    bool operator<(const Pointll &p) const {
        return x < p.x || (x == p.x && y < p.y);
    }
    friend ostream &operator<<(ostream &os, const Pointll &p) {
        return os << '(' << p.x << ',' << p.y << ')';
    }
    friend istream &operator>>(istream &is, Pointll &p) {
        return is >> p.x >> p.y;
    }
} ptll;

int ccw(const ptll &a, ptll b, ptll c) {
    if (a == b) return (a == c ? 0 : +3);  // same point or different
    b = b - a, c = c - a;
    if (sign(b.cross(c)) == +1) return +1;         // "COUNTER_CLOCKWISE"
    if (sign(b.cross(c)) == -1) return -1;         // "CLOCKWISE"
    if (sign(b.dot(c)) == -1) return +2;           // "ON_RAY_b_a"
    if (cmp(b.norm(), c.norm()) == -1) return -2;  // "ON_RAY_a_b"
    return 0;                                      // "ON_SEGMENT"
}

};  // namespace Geometry

using namespace Geometry;

void solve() {
    ptll aa, bb, cc, tt;
    int s;
    cin >> aa >> bb >> cc >> tt >> s;

    auto A = ccw(aa, bb, tt);
    auto B = ccw(aa, bb, cc);

    bool can = abs(A * B) == 1 && A == B && sign(bb.dot(tt, aa)) == 1;

    if (!can) {
        cout << "NO" << endl;
        return;
    }

    pt a = pt(aa.x, aa.y);
    pt b = pt(bb.x, bb.y);
    pt c = pt(cc.x, cc.y);
    pt t = pt(tt.x, tt.y);

    a = a - b;
    b = b - b;
    c = c - b;
    t = t - b;

    if (s == 0) {
        swap(a, c);
    }

    c = c.rotate(-a.ang());
    t = t.rotate(-a.ang());
    a = a.rotate(-a.ang());

    bool isneg = false;

    if (sign(c.y) == -1) {
        isneg = true;
        a.y *= -1;
        b.y *= -1;
        c.y *= -1;
        t.y *= -1;
    }

    if (sign(c.y) == 0) {
        cout << "NO" << endl;
        return;
    }

    // cout << a << endl;
    // cout << a.ang() << endl;

    if (sign(t.x) <= 0 || sign(t.y) <= 0) {
        cout << "NO" << endl;
        return;
    }

    cout << "YES" << endl;

    long double ans = t.ang() * 2 - c.ang();

    if (isneg) {
        ans *= -1;
    }

    cout << fixed << setprecision(10) << ans * 180 / PI << endl;
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(nullptr);
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
}
Editor is loading...
Leave a Comment