Submission #667139

---

Source Code Expand

#include <cstdio>
#include <iostream>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <climits>
#include <cfloat>
#include <functional>
using namespace std;

class Point
{
public:
    int y, x;
    Point(){
        y = x = 0;
    }
    Point(int y0, int x0){
        y = y0;
        x = x0;
    }
    Point operator+(const Point& p) const{
        return Point(y + p.y, x + p.x);
    }
    Point operator-(const Point& p) const{
        return Point(y - p.y, x - p.x);
    }
    Point operator*(int a) const{
        return Point(y * a, x * a);
    }
    bool operator==(const Point& p) const{
        return y == p.y && x == p.x;
    }
    long long length2() const{
        return y * (long long)y + x * (long long)x;
    }
    long long dist2(const Point& p) const{
        return (y - p.y) * (long long)(y - p.y) + (x - p.x) * (long long)(x - p.x);
    }
    long long dot(const Point& p) const{
        return y * (long long)p.y + x * (long long)p.x; // |a|*|b|*cosθ
    }
    long long cross(const Point& p) const{
        return x * (long long)p.y - y * (long long)p.x; // |a|*|b|*sinθ
    }
};

class ConvexHull
{
private:
    class CompareLess{
    public:
        bool operator() (const Point& p1, const Point& p2) const{
            return make_pair(p1.x, p1.y) < make_pair(p2.x, p2.y);
        };
    };
    class CompareGreater{
    public:
        bool operator() (const Point& p1, const Point& p2) const{
            return make_pair(p1.x, p1.y) > make_pair(p2.x, p2.y);
        };
    };
    set<Point, CompareLess>    upperPolygon;
    set<Point, CompareGreater> lowerPolygon;

    template<class Compare>
    void add(const Point& p, set<Point, Compare>& polygon) const
    {
        if(polygon.empty()){
            polygon.insert(p);
            return;
        }
        if(isInside(p, polygon))
            return;

        Point a = *polygon.begin();
        Point b = *polygon.rbegin();
        if(min(a.x, b.x) < p.x && p.x < max(a.x, b.x) && (b - a).cross(p - a) < 0)
            return;

        if(p.x != a.x && p.x == b.x){
            if(Compare()(b, p))
                polygon.erase(--polygon.end());
            else
                return;
        }

        auto it = polygon.insert(p).first;
        for(;;){
            auto it3 = it;
            if(it3 == polygon.begin())
                break;
            -- it3;
            Point d = *it3;

            auto it2 = it3;
            if(it2 == polygon.begin())
                break;
            -- it2;
            Point c = *it2;

            if((d - p).cross(c - p) <= 0)
                polygon.erase(it3);
            else
                break;
        }
        for(;;){
            auto it2 = it;
            ++ it2;
            if(it2 == polygon.end())
                break;
            Point c = *it2;

            auto it3 = it2;
            ++ it3;
            if(it3 == polygon.end())
                break;
            Point d = *it3;

            if((d - p).cross(c - p) <= 0)
                polygon.erase(it2);
            else
                break;
        }
    }

    template<class Compare>
    bool isInside(const Point& p, const set<Point, Compare>& polygon) const
    {
        if(polygon.empty())
            return false;

        Point a = *polygon.begin();
        Point b = *polygon.rbegin();
        if((b - a).cross(p - a) < 0)
            return false;

        auto it2 = polygon.lower_bound(p);
        if(it2 == polygon.end())
            return false;
        Point d = *it2;
        if(it2 == polygon.begin())
            return d == p;

        auto it1 = it2;
        -- it1;
        Point c = *it1;

        return (d - c).cross(p - c) <= 0;
    }

public:
    void add(const Point& p)
    {
        add(p, upperPolygon);
        add(p, lowerPolygon);
    }
    bool isInside(const Point& p) const
    {
        return isInside(p, upperPolygon) || isInside(p, lowerPolygon);
    }
};

int main()
{
    int n;
    cin >> n;

    ConvexHull ch;
    for(int i=0; i<n; ++i){
        string s;
        Point p;
        cin >> s >> p.x >> p.y;

        if(s == "TARGET"){
            if(ch.isInside(p))
                cout << "DANGER" << endl;
            else
                cout << "SAFE" << endl;
        }
        else{
            ch.add(p);
        }
    }

    return 0;
}

Submission Info

Judge Result