Submission #2695297

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;
using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
constexpr ll TEN(int n) { return (n==0) ? 1 : 10*TEN(n-1); }
template<class T> using V = vector<T>;
template<class T> using VV = V<V<T>>;

using D = long long;
const D EPS = 0;
int sgn(D a) { return (abs(a) <= EPS) ? 0 : (a < 0 ? -1 : 1); }
int sgn(D a, D b) { return sgn(a-b); }

struct Pt2 {
    D x, y;
    Pt2() {}
    Pt2(D _x, D _y) : x(_x), y(_y) {}
    Pt2 operator+(const Pt2 &r) const { return Pt2(x+r.x, y+r.y); }
    Pt2 operator-(const Pt2 &r) const { return Pt2(x-r.x, y-r.y); }

    Pt2 operator-() const { return Pt2(-x, -y); }
    
    bool operator<(const Pt2 &r) const { return 2*sgn(x, r.x)+sgn(y, r.y)<0; }
    bool operator==(const Pt2 &r) const { return sgn((*this-r).rabs()) == 0; }
    
    D rabs() const { return max(std::abs(x), std::abs(y)); }
};
ostream& operator<<(ostream& os, const Pt2 &p) {
    return os << "P(" << p.x << ", " << p.y << ")";
}
using P = Pt2;
using Pol = V<P>;

D cross(P a, P b) { return a.x*b.y - a.y*b.x; }
D dot(P a, P b) { return a.x*b.x + a.y*b.y; }

int ccw(P b, P c) {
    int s = sgn(cross(b, c));
    if (s) return s;
    if (!sgn(c.rabs()) || !sgn((c-b).rabs())) return 0;
    if (dot(b, c) < 0) return 2;
    if (dot(-b, c-b) < 0) return -2;
    return 0;
}
int ccw(P a, P b, P c) { return ccw(b-a, c-a); }


struct Convex {
    set<P> pol;
    bool cng(P p) {
        if (pol.size() == 0) return true;
        auto fi = *pol.begin(), ed = *pol.rbegin();
        if (p < fi || ed < p) return true;
        if (p == fi || p == ed) return false;
        auto it = pol.lower_bound(p);
        assert(it != pol.begin());
        auto ri = *it; it--;
        auto le = *it;
        if (ccw(le, ri, p) != 1) return false;
        return true;
    }
    bool lenorm(P p) {
        auto it = pol.lower_bound(p);
        if (it == pol.begin()) return false;
        it--;
        auto ri = *it;
        if (it == pol.begin()) return false;
        it--;
        auto le = *it;
        if (ccw(le, ri, p) == -1) return false;
        pol.erase(ri);
        return true;
    }
    bool rinorm(P p) {
        auto it = pol.lower_bound(p);
        if (it == pol.end()) return false;
        auto le = *it;
        it++;
        if (it == pol.end()) return false;
        auto ri = *it;
        it++;
        if (ccw(p, le, ri) == -1) return false;
        pol.erase(le);
        return true;
    }
    void ins(P p) {
        if (!cng(p)) return;
        while (lenorm(p)) {}
        while (rinorm(p)) {}
        pol.insert(p);
    }
};


int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << setprecision(20) << fixed;

    Convex up, dw;
    int n;
    cin >> n;

    for (int i = 0; i < n; i++) {
        string s;
        D x, y;
        cin >> s >> x >> y;
        P p = P(x, y);
        if (s == "TARGET") {
            bool f1 = up.cng(p);
            bool f2 = dw.cng(-p);
//            cout << f1 << " " << f2 << " " << up.pol.size() << " " << dw.pol.size() << endl;
            if (!f1 && !f2) cout << "DANGER" << endl;
            else cout << "SAFE" << endl;
        } else {
            up.ins(p);
            dw.ins(-p);
        }
    }
    return 0;
}

Submission Info

Judge Result