Submission #84520

---

Source Code Expand

#include<cstdio>
#include<algorithm>
#include<stack>
#include<queue>
#include<vector>
#include<string>
#include<string.h>
#include<cstdlib>
#include<ctime>
#include<cmath>
#include<map>
#include<set>
#include<bitset>
#include<iostream>
#include<sstream>
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < n; i++)
#define rrep(i,n) for(int i = 1; i <= n; i++)
#define drep(i,n) for(int i = n-1; i >= 0; i--)
#define each(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();it++)
#define rng(a) a.begin(),a.end()
#define maxs(x,y) x = max(x,y);
#define mins(x,y) x = min(x,y);
#define pb push_back
#define snuke srand((unsigned)time(NULL))
using namespace std;
typedef long long int ll;
typedef pair<int,int> P;

const int MX = 100005, INF = 1000000000, mod = 1000000009;
const ll LINF = 1000000000000000000ll;
const double eps = 1e-9;
const int dx[4] = {-1,0,1,0}, dy[4] = {0,-1,0,1}; //<^>v


const double EPS = 10e-10;

// 2次元ベクトル
class Point {
public:
	double x, y;
	Point() {}
	Point(double x, double y) : x(x), y(y) {}
	
	Point operator+(Point t) const {
		return Point(x + t.x, y + t.y);
	}
	Point operator-(Point t) const {
		return Point(x - t.x, y - t.y);
	}
	Point operator*(double t) const {
		return Point(x * t, y * t);
	}
	double dot(Point t) const {
		return x * t.x + y * t.y;
	}
	double cross(Point t) const {
		return x * t.y - y * t.x;
	}
	double normSq() const {
		return x * x + y * y;
	}
	double norm() const {
		return sqrt(normSq());
	}
	int ccw(Point a, Point b) const {
		const Point& c = *this;
		if ((b - a).cross(c - a) > EPS)      return +1;
		if ((b - a).cross(c - a) < -EPS)      return -1;
		if ((b - a).dot(c - a)   < EPS)      return +2;
		if ((b - a).norm() < (c - a).norm()) return -2;
		/* otherwise */                      return  0;
		// 上2つのif中の<を<=にすれば端点をexcludeできる
	}
	
	// thisが線分AB上にあるか
	bool isOnLine(Point a, Point b) const {
		return ccw(a, b) == 0;
	}
	
	// thisを中心にaをrad回転
	Point rotate(Point from, double rad) {
		// | to.x | = | cos(rad) -sin(rad) | | from.x - x | + | x |
		// | to.y |   | sin(rad)  cos(rad) | | from.y - y |   | y |
		return Point(
					 cos(rad) * (from.x - x) - sin(rad) * (from.x - x) + x,
					 sin(rad) * (from.x - x) + cos(rad) * (from.y - y) + y);
	}
	
	bool operator<(Point t) const {
		return x != t.x ? x < t.x : y < t.y;
	}
	bool operator==(Point t) const {
		return abs(x - t.x) <= EPS && abs(y - t.y) <= EPS;
	}
};


typedef Point V;

set<V> up, dw;
typedef set<V>::iterator sit;

void pri(){
	each(it,up){
		printf("(%.0f,%.0f) ",(*it).x,(*it).y);
	} puts("");
	each(it,dw){
		printf("(%.0f,%.0f) ",(*it).x,(*it).y);
	} puts("");
}

int main(){
	int n, x, y;
	char in[10];
	scanf("%d",&n);
	rep(i,n){
		scanf("%s%d%d",in,&x,&y);
		V v = V(x,y); //pri();
		if(in[0] == 'M'){
			sit uit = up.lower_bound(v);
			sit dit = dw.lower_bound(v);
			int flag = 0;
			if(uit == up.end() || uit == up.begin()){
				uit = up.insert(v).fi;
				dit = dw.insert(v).fi;
				flag = 3;
			} else {
				V uv = (*uit); --uit; V uu = (*uit);
				V dv = (*dit); --dit; V du = (*dit);
				if(v.ccw(uu,uv) == +1){
					uit = up.insert(v).fi;
					flag = 1;
				}
				if(v.ccw(du,dv) == -1){
					dit = dw.insert(v).fi;
					flag = 2;
				}
			}
			
			if(flag&1){
				sit it = up.find(v);
				if(it != up.begin()){
					--it;
					while(it != up.begin()){
						V uv = (*it);
						--it;
						V uu = (*it);
						if(uv.ccw(v,uu) != -1){
							++it;
							up.erase(it++);
							--it;
						} else break;
					}
				}
				it = up.find(v); ++it;
				if(it != up.end()){
					while(1){
						V uv = (*it);
						++it;
						if(it == up.end()) break;
						V uu = (*it);
						if(uv.ccw(v,uu) != +1){
							--it;
							up.erase(it++);
						} else break;
					}
				}
			}
			if(flag&2){
				sit it = dw.find(v);
				if(it != dw.begin()){
					--it;
					while(it != dw.begin()){
						V uv = (*it);
						--it;
						V uu = (*it);
						if(uv.ccw(v,uu) != +1){
							++it;
							dw.erase(it++);
							--it;
						} else break;
					}
				}
				it = dw.find(v); ++it;
				if(it != dw.end()){
					while(1){
						V uv = (*it);
						++it;
						if(it == dw.end()) break;
						V uu = (*it);
						if(uv.ccw(v,uu) != -1){
							--it;
							dw.erase(it++);
						} else break;
					}
				}
			}
		} else {
			sit uit = up.lower_bound(v);
			sit dit = dw.lower_bound(v);
			if((*uit) == v || (*dit) == v){ puts("DANGER"); continue;}
			if(uit == up.end() || uit == up.begin()){
				puts("SAFE");
				continue;
			}
			V uv = (*uit); --uit; V uu = (*uit);
			V dv = (*dit); --dit; V du = (*dit);
			if(v.ccw(uu,uv) == +1 || v.ccw(du,dv) == -1){
				//printf("(%.0f,%.0f)(%.0f,%.0f)(%.0f,%.0f) %d\n",v.x,v.y,uu.x,uu.y,uv.x,uv.y,v.ccw(uu,uv));
				//printf("(%.0f,%.0f)(%.0f,%.0f)(%.0f,%.0f) %d\n",v.x,v.y,du.x,du.y,dv.x,dv.y,v.ccw(du,dv));
				puts("SAFE");
				continue;
			}
			puts("DANGER");
		}
	}
	
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:117:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
./Main.cpp:119:27: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]

Judge Result