제출 #542788

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
542788		shcal	Balloons (CEOI11_bal)	Java	100 / 100	1965 ms	33200 KiB

bal

import java.io.FileInputStream;
import java.io.FileWriter;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.InputMismatchException;
import java.util.Stack;
import java.util.StringTokenizer;

// https://oj.uz/problem/view/CEOI11_bal
public class bal {
	public static void main(String[] args) throws IOException {
		FastIO io = new FastIO();
		
		int n = io.nextInt();
		
		Stack<Pair> s = new Stack<>();
		
		StringTokenizer token;
		for (int i = 0; i < n; i++) {
			double x = io.nextDouble();
			double r = io.nextDouble();
			
			while (!s.isEmpty()) {
				double x1 = s.peek().first;
				double r1 = s.peek().second;
				r = Math.min(r, (x-x1)*(x-x1)/(4.0*r1));
				if (r >= r1) s.pop();
				else break;
			}
			
			io.printf("%.3f\n", r);
			
			s.push(new Pair(x, r));
		}
		
		io.close();
	}
}

class Pair {
	double first;
	double second;
	
	public Pair (double f, double s) {
		first = f;
		second = s;
	}
}

class FastIO extends PrintWriter {
	private InputStream stream;
	private byte[] buf = new byte[1 << 16];
	private int curChar;
	private int numChars;

	// standard input
	public FastIO() { this(System.in, System.out); }

	public FastIO(InputStream i, OutputStream o) {
		super(o);
		stream = i;
	}

	// file input
	public FastIO(String i, String o) throws IOException {
		super(new FileWriter(o));
		stream = new FileInputStream(i);
	}

	// throws InputMismatchException() if previously detected end of file
	private int nextByte() {
		if (numChars == -1) {
			throw new InputMismatchException();
		}
		if (curChar >= numChars) {
			curChar = 0;
			try {
				numChars = stream.read(buf);
			} catch (IOException e) {
				throw new InputMismatchException();
			}
			if (numChars == -1) {
				return -1;  // end of file
			}
		}
		return buf[curChar++];
	}

	// to read in entire lines, replace c <= ' '
	// with a function that checks whether c is a line break
	public String next() {
		int c;
		do {
			c = nextByte();
		} while (c <= ' ');

		StringBuilder res = new StringBuilder();
		do {
			res.appendCodePoint(c);
			c = nextByte();
		} while (c > ' ');
		return res.toString();
	}

	public int nextInt() {  // nextLong() would be implemented similarly
		int c;
		do {
			c = nextByte();
		} while (c <= ' ');

		int sgn = 1;
		if (c == '-') {
			sgn = -1;
			c = nextByte();
		}

		int res = 0;
		do {
			if (c < '0' || c > '9') {
				throw new InputMismatchException();
			}
			res = 10 * res + c - '0';
			c = nextByte();
		} while (c > ' ');
		return res * sgn;
	}

	public double nextDouble() { return Double.parseDouble(next()); }
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10