Submission #125680

---

Source Code Expand

#include<iostream>
#include<algorithm>
#include<set>
#include<string>

using namespace std;

string s;


struct P{
	double x, y;
	P(){};
	P(double a, double b){
		x = a;
		y = b;
	}
	P operator-(P a){
		return P(x - a.x, y - a.y);
	}
	P operator+(P a){
		return P(x + a.x, y + a.y);
	}

};       

namespace std{
	bool operator<(const P& a, const P& b){
		if(a.x == b.x)return a.y < b.y;
		return a.x < b.x;
	}
}

double det(P a, P b){
	return a.x * b.y - b.x * a.y;
}

int ccw(P a, P b, P c){
	c = c - a;
	b = b - a;
	if(det(b, c) > 0)return 1;
	if(det(b, c) < 0)return -1;
	return 0;
}

void add_upper(set<P> &uc, P p){
	if(uc.size() < 2)uc.insert(p);
	else{
		auto it = uc.lower_bound(p);
		if(it != uc.begin() && it != uc.end() && ccw(*prev(it), *it, p) <= 0)return;
		if(it != uc.end())
			for(auto jt = it;next(jt) != uc.end() && ccw(*jt, *next(jt), p) >= 0;uc.erase(jt++));
		it = uc.lower_bound(p);
		if(it != uc.begin())
			for(auto jt = prev(it);jt != uc.begin() && ccw(*jt, *prev(jt), p) <= 0;uc.erase(jt--));
		uc.insert(p);
	}
}

void add_lower(set<P> &lc, P p){
	if(lc.size() < 2)lc.insert(p);
	else{
		auto it = lc.lower_bound(p);
		if(it != lc.begin() && it != lc.end() && ccw(*prev(it), *it, p) >= 0)return;
		if(it != lc.end())
			for(auto jt = it;next(jt) != lc.end() && ccw(*jt, *next(jt), p) <= 0;lc.erase(jt++));
		it = lc.lower_bound(p);
		if(it != lc.begin())
			for(auto jt = prev(it);jt != lc.begin() && ccw(*jt, *prev(jt), p) >= 0;lc.erase(jt--));
		lc.insert(p);
	}
}

bool inside(set<P> &uc, set<P> &lc, P p){
	if(uc.size() < 2)return false;

	auto uit = uc.lower_bound(p);
	auto lit = lc.lower_bound(p);
	if(uit == uc.begin() || lit == lc.begin() || uit == uc.end() || lit == lc.end())return false;
	if(ccw(*prev(uit), *uit, p) > 0)return false;
	if(ccw(*prev(lit), *lit, p) < 0)return false;
	return true;
}




int main(){
	int n;
	double x, y;
	set<P> lc, uc;
	cin >> n;
	for(int i = 0;i < n;i++){
		cin >> s >> x >> y;
		if(s == "MONITOR"){
			add_upper(uc, P(x, y));
			add_lower(lc, P(x, y));
		}
		else{
			if(inside(uc, lc, P(x, y))){
				cout << "DANGER" << endl;
			}
			else{
				cout << "SAFE" << endl;
			}
		}
	}
	return 0;
}

Submission Info

Judge Result