Submission #85302

---

Source Code Expand

import java.awt.geom.Line2D;
import java.awt.geom.Point2D;
import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Comparator;
import java.util.InputMismatchException;
import java.util.TreeSet;

public class Main {
	static InputStream is;
	static PrintWriter out;
	static String INPUT = "";
	
	static void solve()
	{
		int n = ni();
		IncrementalConvexHull ich = new IncrementalConvexHull();
		for(int i = 0;i < n;i++){
			char c = ns().toCharArray()[0];
			int x = ni(), y = ni();
			if(c == 'T'){
				if(ich.includes(x, y)){
					out.println("DANGER");
				}else{
					out.println("SAFE");
				}
			}else{
				ich.add(x, y);
			}
		}
	}
	
	public static class IncrementalConvexHull {
		public TreeSet<Vertex> hull;
		public Vertex center = null;
		
		public IncrementalConvexHull() {
			hull = new TreeSet<Vertex>(new Comparator<Vertex>(){
				@Override
				public int compare(Vertex a, Vertex b) {
//					if(center == null)return Double.compare(a.arg(0, 0), b.arg(0, 0));
					if(a.x == b.x && a.y == b.y)return 0;
					if(a.x == center.x && a.y == center.y)return -1;
					if(b.x == center.x && b.y == center.y)return 1;
					return Double.compare(a.arg(center.x, center.y), b.arg(center.x, center.y));
				}
			});
		}
		
		public boolean add(double x, double y)
		{
			if(includes(x, y))return false;
			if(hull.size() <= 1){
				// 何も考えずに追加
				if(hull.size() == 1){
					center = new Vertex((hull.first().x+x)/2, (hull.first().y+y)/2);
				}
				hull.add(new Vertex(x, y));
				return true;
			}else if(hull.size() == 2){
				Vertex v = new Vertex(x, y);
				Vertex f = hull.first();
				Vertex c = hull.last();
				if(isACB(center.x, center.y, v.x, v.y, f.x, f.y)){
					hull.remove(f);
					hull.add(v);
					return true;
				}
				if(isACB(center.x, center.y, v.x, v.y, c.x, c.y)){
					hull.remove(c);
					hull.add(v);
					return true;
				}
				hull.add(v);
				return true;
			}else{
				Vertex v = new Vertex(x, y);
				Vertex f = hull.floor(v);
				Vertex c = null;
				if(f == null){
					f = hull.last();
					c = hull.first();
				}else{
					c = hull.higher(f);
					if(c == null)c = hull.first();
				}
				
				
				// 反時計回り側
				while(hull.size() > 1){
					Vertex nc = hull.higher(c);
					if(nc == null)nc = hull.first();
					// ncがv-cの上にあるならcを除く
					double cross = (nc.x-v.x)*(c.y-v.y)-(nc.y-v.y)*(c.x-v.x);
					if(cross >= 0){
						hull.remove(c);
						c = nc;
					}else{
						break;
					}
				}
				
				// 時計回り側
				while(hull.size() > 1){
					Vertex nf = hull.lower(f);
					if(nf == null)nf = hull.last();
//					U.tr("v", v, "c", f, "nc", nf);
					// nfがv-fの下にあるならfを除く
					double cross = (nf.x-v.x)*(f.y-v.y)-(nf.y-v.y)*(f.x-v.x);
					if(cross <= 0){
						hull.remove(f);
						f = nf;
					}else{
						break;
					}
				}
//				double thres = -1E-9;
//				while(!hull.isEmpty()){
//					Vertex nc = hull.higher(c);
//					if(nc == null)nc = hull.first();
//					// ncがv-cの上にあるならcを除く
//					double cross = (nc.x-v.x)*(c.y-v.y)-(nc.y-v.y)*(c.x-v.x);
//					if(cross >= thres){
//						if(cross < 1E-9)cross = 1E-9;
//						hull.remove(c);
//						c = nc;
//					}else{
//						break;
//					}
//				}
//				
//				// 時計回り側
//				thres = 1E-9;
//				while(!hull.isEmpty()){
//					Vertex nf = hull.lower(f);
//					if(nf == null)nf = hull.last();
////					U.tr("v", v, "c", f, "nc", nf);
//					// nfがv-fの下にあるならfを除く
//					double cross = (nf.x-v.x)*(f.y-v.y)-(nf.y-v.y)*(f.x-v.x);
//					if(cross <= thres){
//						if(cross > -1E-9)cross = -1E-9;
//						hull.remove(f);
//						f = nf;
//					}else{
//						break;
//					}
//				}
				hull.add(v);
				return true;
			}
		}
		
		public boolean includes(double x, double y)
		{
			if(hull.isEmpty())return false;
			if(hull.size() == 1)return Point2D.distance(x, y, hull.first().x, hull.first().y) < 1E-9;
			if(hull.size() == 2)return Line2D.ptSegDist(hull.first().x, hull.first().y, hull.last().x, hull.last().y, x, y) < 1E-9;
//			if(Point2D.distance(x, y, center.x, center.y) < 1E-9)return true;
			
			// O(log N)
			Vertex v = new Vertex(x, y);
			Vertex f = hull.floor(v);
			Vertex c;
			if(f == null){
				f = hull.last();
				c = hull.first();
			}else{
				c = hull.higher(f);
				if(c == null)c = hull.first();
			}
			// on
			if(Line2D.ptSegDist(f.x, f.y, c.x, c.y, v.x, v.y) < 1E-9)return true;
//			U.tr(f.x, f.y, c.x, c.y, v.x, v.y, Line2D.relativeCCW(f.x, f.y, c.x, c.y, v.x, v.y));
			if(isACB(center.x, center.y, v.x, v.y, f.x, f.y))return false;
			if(isACB(center.x, center.y, v.x, v.y, c.x, c.y))return false;
			if(Line2D.relativeCCW(f.x, f.y, c.x, c.y, v.x, v.y) == -1)return true;
			return false;
		}
		
		static boolean isACB(double ax, double ay, double bx, double by, double cx, double cy)
		{
			if((ax == cx && ay == cy) || (bx == cx && by == cy))return true;
			return Math.abs(((cx-ax)*(by-ay)-(cy-ay)*(bx-ax))/Point2D.distance(ax, ay, bx, by)/Point2D.distance(ax, ay, cx, cy)) < 1E-9
					&& (cx-ax)*(cx-bx)+(cy-ay)*(cy-by) <= 0;
		}
		
		static class Vertex
		{
			public double x, y;
			
			public Vertex(double x, double y) {
				this.x = x; this.y = y;
			}
			
			public double arg(double gx, double gy)
			{
				return Math.atan2(y-gy, x-gx);
			}
			
			public String toString()
			{
				return String.format("(%.3f,%.3f)", x, y);
			}
		}
	}
	
	public static void main(String[] args) throws Exception
	{
		long S = System.currentTimeMillis();
		is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());
		out = new PrintWriter(System.out);
		
		solve();
		out.flush();
		long G = System.currentTimeMillis();
		tr(G-S+"ms");
	}
	
	private static boolean eof()
	{
		if(lenbuf == -1)return true;
		int lptr = ptrbuf;
		while(lptr < lenbuf)if(!isSpaceChar(inbuf[lptr++]))return false;
		
		try {
			is.mark(1000);
			while(true){
				int b = is.read();
				if(b == -1){
					is.reset();
					return true;
				}else if(!isSpaceChar(b)){
					is.reset();
					return false;
				}
			}
		} catch (IOException e) {
			return true;
		}
	}
	
	private static byte[] inbuf = new byte[1024];
	private static int lenbuf = 0, ptrbuf = 0;
	
	private static int readByte()
	{
		if(lenbuf == -1)throw new InputMismatchException();
		if(ptrbuf >= lenbuf){
			ptrbuf = 0;
			try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); }
			if(lenbuf <= 0)return -1;
		}
		return inbuf[ptrbuf++];
	}
	
	private static boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); }
	private static int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; }
	
	private static double nd() { return Double.parseDouble(ns()); }
	private static char nc() { return (char)skip(); }
	
	private static String ns()
	{
		int b = skip();
		StringBuilder sb = new StringBuilder();
		while(!(isSpaceChar(b))){ // when nextLine, (isSpaceChar(b) && b != ' ')
			sb.appendCodePoint(b);
			b = readByte();
		}
		return sb.toString();
	}
	
	private static char[] ns(int n)
	{
		char[] buf = new char[n];
		int b = skip(), p = 0;
		while(p < n && !(isSpaceChar(b))){
			buf[p++] = (char)b;
			b = readByte();
		}
		return n == p ? buf : Arrays.copyOf(buf, p);
	}
	
	private static char[][] nm(int n, int m)
	{
		char[][] map = new char[n][];
		for(int i = 0;i < n;i++)map[i] = ns(m);
		return map;
	}
	
	private static int[] na(int n)
	{
		int[] a = new int[n];
		for(int i = 0;i < n;i++)a[i] = ni();
		return a;
	}
	
	private static int ni()
	{
		int num = 0, b;
		boolean minus = false;
		while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
		if(b == '-'){
			minus = true;
			b = readByte();
		}
		
		while(true){
			if(b >= '0' && b <= '9'){
				num = num * 10 + (b - '0');
			}else{
				return minus ? -num : num;
			}
			b = readByte();
		}
	}
	
	private static long nl()
	{
		long num = 0;
		int b;
		boolean minus = false;
		while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
		if(b == '-'){
			minus = true;
			b = readByte();
		}
		
		while(true){
			if(b >= '0' && b <= '9'){
				num = num * 10 + (b - '0');
			}else{
				return minus ? -num : num;
			}
			b = readByte();
		}
	}
	
	private static void tr(Object... o) { if(INPUT.length() != 0)System.out.println(Arrays.deepToString(o)); }
}

Submission Info

Judge Result