Submission #1548550
Source Code Expand
// package agc.agc019; import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import java.util.*; public class Main { public static void main(String[] args) { InputReader in = new InputReader(System.in); PrintWriter out = new PrintWriter(System.out); int x1 = in.nextInt(); int y1 = in.nextInt(); int x2 = in.nextInt(); int y2 = in.nextInt(); int n = in.nextInt(); int[][] fountains = new int[n][2]; for (int i = 0; i < n ; i++) { for (int j = 0; j < 2 ; j++) { fountains[i][j] = in.nextInt(); } } int minX = Math.min(x1, x2); int maxX = Math.max(x1, x2); int minY = Math.min(y1, y2); int maxY = Math.max(y1, y2); List<int[]> availablefountains = new ArrayList<>(); for (int i = 0 ; i < n ; i++) { if (minX <= fountains[i][0] && fountains[i][0] <= maxX) { if (minY <= fountains[i][1] && fountains[i][1] <= maxY) { availablefountains.add(new int[]{ Math.abs(x1-fountains[i][0]), Math.abs(y1-fountains[i][1])}); } } } out.println(String.format("%.15f", solve(maxX-minX, maxY-minY, availablefountains))); out.flush(); } static final double HALF = 20 * Math.PI / 2; static final double QUARTER = HALF / 2; static final double CORNER = 20; static final double HALF_LOSS = HALF - CORNER; static final double QUARTER_GAIN = QUARTER - CORNER; static final double LATTICE_SIZE = 100; private static double solve(int W, int H, List<int[]> fountains) { int n = fountains.size(); Collections.sort(fountains, (u, v) -> u[0] - v[0]); int[] a = new int[n]; for (int i = 0; i < n ; i++) { a[i] = fountains.get(i)[1]; } int x = lis(a); double base = (W + H) * LATTICE_SIZE; if (x == Math.min(W, H) + 1) { if (x == 1) { return base + HALF_LOSS; } return base + (x - 1) * QUARTER_GAIN + HALF_LOSS; } return base + x * QUARTER_GAIN; } /** * Computes longest increasing sequence. * If you want to get actual sequence, see dp[1..ans]. * <p> * O(nlogn) * * @param values * @return */ public static int lis(int[] values) { int n = values.length; long[] lval = new long[n]; for (int i = 0; i < values.length; i++) { lval[i] = values[i] * 1000000000L + i; } int ans = 0; long[] dp = new long[n + 1]; Arrays.fill(dp, Long.MIN_VALUE); for (int i = 0; i < n; i++) { int idx = Arrays.binarySearch(dp, 0, ans + 1, lval[i]); if (idx < 0) { idx = -idx - 2; dp[idx + 1] = lval[i]; if (idx >= ans) { ans++; } } } return ans; } public static void debug(Object... o) { System.err.println(Arrays.deepToString(o)); } public static class InputReader { private static final int BUFFER_LENGTH = 1 << 12; private InputStream stream; private byte[] buf = new byte[BUFFER_LENGTH]; private int curChar; private int numChars; public InputReader(InputStream stream) { this.stream = stream; } private int next() { if (numChars == -1) { throw new InputMismatchException(); } if (curChar >= numChars) { curChar = 0; try { numChars = stream.read(buf); } catch (IOException e) { throw new InputMismatchException(); } if (numChars <= 0) return -1; } return buf[curChar++]; } public char nextChar() { return (char) skipWhileSpace(); } public String nextToken() { int c = skipWhileSpace(); StringBuilder res = new StringBuilder(); do { res.append((char) c); c = next(); } while (!isSpaceChar(c)); return res.toString(); } public int nextInt() { return (int) nextLong(); } public long nextLong() { int c = skipWhileSpace(); long sgn = 1; if (c == '-') { sgn = -1; c = next(); } long res = 0; do { if (c < '0' || c > '9') { throw new InputMismatchException(); } res *= 10; res += c - '0'; c = next(); } while (!isSpaceChar(c)); return res * sgn; } public double nextDouble() { return Double.valueOf(nextToken()); } int skipWhileSpace() { int c = next(); while (isSpaceChar(c)) { c = next(); } return c; } boolean isSpaceChar(int c) { return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1; } } }
Submission Info
Submission Time | |
---|---|
Task | C - Fountain Walk |
User | hamadu |
Language | Java8 (OpenJDK 1.8.0) |
Score | 900 |
Code Size | 5571 Byte |
Status | AC |
Exec Time | 612 ms |
Memory | 53540 KB |
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 900 / 900 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | sample_01.txt, sample_02.txt, sample_03.txt |
All | sample_01.txt, sample_02.txt, sample_03.txt, sample_01.txt, sample_02.txt, sample_03.txt, subtask_1_01.txt, subtask_1_02.txt, subtask_1_03.txt, subtask_1_04.txt, subtask_1_05.txt, subtask_1_06.txt, subtask_1_07.txt, subtask_1_08.txt, subtask_1_09.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt, subtask_1_14.txt, subtask_1_15.txt, subtask_1_16.txt, subtask_1_17.txt, subtask_1_18.txt, subtask_1_19.txt, subtask_1_20.txt, subtask_1_21.txt, subtask_1_22.txt, subtask_1_23.txt, subtask_1_24.txt, subtask_1_25.txt, subtask_1_26.txt, subtask_1_27.txt, subtask_1_28.txt, subtask_1_29.txt, subtask_1_30.txt, subtask_1_31.txt, subtask_1_32.txt, subtask_1_33.txt, subtask_1_34.txt, subtask_1_35.txt, subtask_1_36.txt, subtask_1_37.txt, subtask_1_38.txt, subtask_1_39.txt, subtask_1_40.txt, subtask_1_41.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
sample_01.txt | AC | 156 ms | 25812 KB |
sample_02.txt | AC | 144 ms | 26068 KB |
sample_03.txt | AC | 146 ms | 24404 KB |
subtask_1_01.txt | AC | 155 ms | 25812 KB |
subtask_1_02.txt | AC | 151 ms | 23636 KB |
subtask_1_03.txt | AC | 158 ms | 23764 KB |
subtask_1_04.txt | AC | 154 ms | 24404 KB |
subtask_1_05.txt | AC | 149 ms | 25684 KB |
subtask_1_06.txt | AC | 157 ms | 28500 KB |
subtask_1_07.txt | AC | 155 ms | 26324 KB |
subtask_1_08.txt | AC | 156 ms | 26580 KB |
subtask_1_09.txt | AC | 192 ms | 24996 KB |
subtask_1_10.txt | AC | 199 ms | 29972 KB |
subtask_1_11.txt | AC | 173 ms | 22100 KB |
subtask_1_12.txt | AC | 429 ms | 52336 KB |
subtask_1_13.txt | AC | 208 ms | 27616 KB |
subtask_1_14.txt | AC | 190 ms | 24408 KB |
subtask_1_15.txt | AC | 190 ms | 23764 KB |
subtask_1_16.txt | AC | 435 ms | 47056 KB |
subtask_1_17.txt | AC | 193 ms | 25992 KB |
subtask_1_18.txt | AC | 194 ms | 25552 KB |
subtask_1_19.txt | AC | 187 ms | 27488 KB |
subtask_1_20.txt | AC | 455 ms | 51052 KB |
subtask_1_21.txt | AC | 441 ms | 53540 KB |
subtask_1_22.txt | AC | 417 ms | 50492 KB |
subtask_1_23.txt | AC | 452 ms | 51004 KB |
subtask_1_24.txt | AC | 151 ms | 23636 KB |
subtask_1_25.txt | AC | 143 ms | 26324 KB |
subtask_1_26.txt | AC | 147 ms | 23504 KB |
subtask_1_27.txt | AC | 164 ms | 26324 KB |
subtask_1_28.txt | AC | 229 ms | 30296 KB |
subtask_1_29.txt | AC | 229 ms | 32028 KB |
subtask_1_30.txt | AC | 432 ms | 52104 KB |
subtask_1_31.txt | AC | 266 ms | 53164 KB |
subtask_1_32.txt | AC | 277 ms | 44648 KB |
subtask_1_33.txt | AC | 271 ms | 51744 KB |
subtask_1_34.txt | AC | 281 ms | 53096 KB |
subtask_1_35.txt | AC | 612 ms | 44700 KB |
subtask_1_36.txt | AC | 279 ms | 52892 KB |
subtask_1_37.txt | AC | 287 ms | 52960 KB |
subtask_1_38.txt | AC | 280 ms | 52832 KB |
subtask_1_39.txt | AC | 289 ms | 51100 KB |
subtask_1_40.txt | AC | 288 ms | 52788 KB |
subtask_1_41.txt | AC | 289 ms | 47148 KB |