Submission #84074

---

Source Code Expand

#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;

double EPS = 1e-7;

struct convex
{
	int N;
	int x[200000];
	int y[200000];
	int sum[1<<19];
	int sgn;
	static const int BIT = 1<<18;

	convex(){ }

	convex(int N, int* Xs, int sg)
	{
		this->N = N;
		for(int i=0;i<N;i++){
			x[i] = Xs[i];
			y[i] = -1;
		}
		for(int i=0;i<2*BIT;i++) sum[i] = 0;

		sgn = sg;
	}

	void set(int p, int v)
	{
		p += BIT;
		sum[p] = v; p >>= 1;
		while(p){
			sum[p] = sum[p*2] + sum[p*2+1];
			p >>= 1;
		}
	}

	int query(int r)
	{
		r += BIT;
		int ret = 0;
		while(r){
			if(r&1) ret += sum[--r];
			r >>= 1;
		}
		return ret;
	}

	int left(int p)
	{
		if(p <= 0) return -1;

		int bas = query(p);
		if(bas == 0) return -1;

		int ret = 1;
		while(ret < BIT){
			if(bas > sum[ret*2]){
				bas -= sum[ret*2];
				ret = ret*2+1;
			}else{
				ret = ret*2;
			}
		}

		return ret - BIT;
	}

	int right(int p)
	{
		if(p == -1) return -1;

		int bas = query(p+1)+1;
		
		int ret = 1;
		while(ret < BIT){
			if(bas > sum[ret*2]){
				bas -= sum[ret*2];
				ret = ret*2+1;
			}else{
				ret = ret*2;
			}
		}

		if(ret == 2*BIT - 1) return -1;

		return ret - BIT;
	}

	double at(int xv)
	{
		int ps = lower_bound(x, x+N, xv) - x;
		if(query(ps+1) == 0) return -1;
		
		if(y[ps] != -1) return y[ps];
		int lf = left(ps), rg = right(ps);
		//printf(" %d %d %d %d\n", ps, query(1), lf, rg);
		if(lf == -1 || rg == -1) return -1;

		return y[lf] + (y[rg] - y[lf]) * (double)(x[ps] - x[lf]) / (double)(x[rg] - x[lf]);
	}

	void update(int xv, int yv)
	{
		double a = at(xv);

		int ps = lower_bound(x, x+N, xv) - x;
		
		//printf("%f %d(%d) %d\n", a, xv, ps, yv);

		if(a < 0){
			set(ps, 1);
			y[ps] = yv;
		}else{
			if((yv-a)*sgn > 0){
				set(ps, 1);
				y[ps] = yv;
			}else return;
		}

		//printf("(%d)", sgn);
		//for(int i=0;i<N;i++) printf("%d:%d ", x[i], y[i]);
		//puts("");

		int p1=right(ps); int p2=right(p1);
		while(p2 != -1){
			double nv = y[p1] + (y[p2] - y[p1]) * (double)(x[ps] - x[p1]) / (double)(x[p2] - x[p1]);
			if((yv - nv)*sgn < EPS) break;

			set(p1, 0);
			y[p1] = -1;
			int tmp = right(p2);
			p1 = p2; p2 = tmp;
		}

		p1=left(ps); p2=left(p1);
		//printf("%d %d %d %d %d\n", ps, p1, p2, sum[2], query(2));
		while(p2 != -1){
			double nv = y[p1] + (y[p2] - y[p1]) * (double)(x[ps] - x[p1]) / (double)(x[p2] - x[p1]);
			if((yv - nv)*sgn < EPS) break;

			set(p1, 0);
			y[p1] = -1;
			int tmp = left(p2);
			p1 = p2; p2 = tmp;
		}
	}

};

convex upp, low;

int N;
bool T[200000]; int X[200000], Y[200000];

char S[50]; int x, y;
int Xs[200000], Xl;

int main()
{
	for(;~scanf("%d", &N);){
	for(int i=0;i<N;i++){
		scanf("%s%d%d", S, &x, &y);
		T[i] = S[0]=='T' ? false : true;
		X[i] = x; Y[i] = y;
		Xs[i] = x;
	}

	sort(Xs, Xs+N);
	Xl = unique(Xs, Xs+N) - Xs;

	upp = convex(Xl, Xs, 1);
	low = convex(Xl, Xs, -1);

	for(int i=0;i<N;i++){
		if(T[i]){
			upp.update(X[i], Y[i]);
			low.update(X[i], Y[i]);
		}else{
			double upv = upp.at(X[i]), lwv = low.at(X[i]);
			//printf("%f %f\n", lwv, upv);
			if(upv > 0){
				if(lwv-EPS < Y[i] && Y[i] < upv+EPS){
					puts("DANGER");
					continue;
				}
			}
			puts("SAFE");
		}
	}
	}
	return 0;
}

Submission Info

Compile Error

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

Judge Result