Submission #1542174
Source Code Expand
import java.io.*; import java.util.*; public class Main { boolean in(int p, int q, int x) { // is x in segment p-q(inclusive) return (p <= x && x <= q) || (q <= x && x <= p); } static class Point implements Comparable<Point> { int x, y; public Point(int x, int y) { this.x = x; this.y = y; } @Override public int compareTo(Point o) { return Integer.compare(x, o.x); } } void submit() { int x1 = nextInt(); int y1 = nextInt(); int x2 = nextInt(); int y2 = nextInt(); int n = nextInt(); Point[] a = new Point[n]; int ptr = 0; for (int i = 0; i < n; i++) { int x = nextInt(); int y = nextInt(); if (!in(x1, x2, x) || !in(y1, y2, y)) { continue; } x = Math.abs(x - x1); y = Math.abs(y - y1); a[ptr++] = new Point(x, y); } a = Arrays.copyOf(a, ptr); int dx = Math.abs(x2 - x1); int dy = Math.abs(y2 - y1); if (dx > dy) { int tmp = dy; dy = dx; dx = tmp; for (Point p : a) { tmp = p.x; p.x = p.y; p.y = tmp; } } Arrays.sort(a); long base = 100L * (dx + dy); int[] arr = new int[a.length]; for (int i = 0; i < a.length; i++) { arr[i] = a[i].y; } int[] aux = new int[a.length + 2]; Arrays.fill(aux, Integer.MAX_VALUE); aux[0] = Integer.MIN_VALUE; int ans = 0; for (int x : arr) { int low = 0; // < int high = ans + 1; // >= while (high - low > 1) { int mid = (low + high) >> 1; if (aux[mid] < x) { low = mid; } else { high = mid; } } aux[high] = x; if (high == ans + 1) { ans++; } } double ret = base - BONUS * ans; if (a.length == dx + 1 && ans == a.length) { ret += BONUS; ret += PENALTY; } out.println(ret); } static final double BONUS = 20 - 5 * Math.PI; static final double PENALTY = 10 * Math.PI - 20; void preCalc() { } void stress() { } void test() { } Main() throws IOException { br = new BufferedReader(new InputStreamReader(System.in)); out = new PrintWriter(System.out); preCalc(); submit(); // stress(); // test(); out.close(); } static final Random rng = new Random(); static int rand(int l, int r) { return l + rng.nextInt(r - l + 1); } public static void main(String[] args) throws IOException { new Main(); } BufferedReader br; PrintWriter out; StringTokenizer st; String nextToken() { while (st == null || !st.hasMoreTokens()) { try { st = new StringTokenizer(br.readLine()); } catch (IOException e) { throw new RuntimeException(e); } } return st.nextToken(); } String nextString() { try { return br.readLine(); } catch (IOException e) { throw new RuntimeException(e); } } int nextInt() { return Integer.parseInt(nextToken()); } long nextLong() { return Long.parseLong(nextToken()); } double nextDouble() { return Double.parseDouble(nextToken()); } }
Submission Info
Submission Time | |
---|---|
Task | C - Fountain Walk |
User | mmaxio |
Language | Java8 (OpenJDK 1.8.0) |
Score | 900 |
Code Size | 3080 Byte |
Status | AC |
Exec Time | 607 ms |
Memory | 53308 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 | 73 ms | 21332 KB |
sample_02.txt | AC | 72 ms | 19156 KB |
sample_03.txt | AC | 71 ms | 19284 KB |
subtask_1_01.txt | AC | 70 ms | 18260 KB |
subtask_1_02.txt | AC | 71 ms | 18772 KB |
subtask_1_03.txt | AC | 72 ms | 18260 KB |
subtask_1_04.txt | AC | 78 ms | 19156 KB |
subtask_1_05.txt | AC | 71 ms | 19284 KB |
subtask_1_06.txt | AC | 71 ms | 20308 KB |
subtask_1_07.txt | AC | 72 ms | 20564 KB |
subtask_1_08.txt | AC | 71 ms | 18260 KB |
subtask_1_09.txt | AC | 207 ms | 38420 KB |
subtask_1_10.txt | AC | 248 ms | 42848 KB |
subtask_1_11.txt | AC | 163 ms | 32896 KB |
subtask_1_12.txt | AC | 598 ms | 53308 KB |
subtask_1_13.txt | AC | 261 ms | 45448 KB |
subtask_1_14.txt | AC | 202 ms | 37444 KB |
subtask_1_15.txt | AC | 194 ms | 31396 KB |
subtask_1_16.txt | AC | 551 ms | 52004 KB |
subtask_1_17.txt | AC | 229 ms | 40044 KB |
subtask_1_18.txt | AC | 219 ms | 38808 KB |
subtask_1_19.txt | AC | 213 ms | 38904 KB |
subtask_1_20.txt | AC | 578 ms | 51852 KB |
subtask_1_21.txt | AC | 598 ms | 52388 KB |
subtask_1_22.txt | AC | 539 ms | 52708 KB |
subtask_1_23.txt | AC | 607 ms | 50116 KB |
subtask_1_24.txt | AC | 72 ms | 19284 KB |
subtask_1_25.txt | AC | 72 ms | 18772 KB |
subtask_1_26.txt | AC | 72 ms | 21204 KB |
subtask_1_27.txt | AC | 71 ms | 19412 KB |
subtask_1_28.txt | AC | 267 ms | 42776 KB |
subtask_1_29.txt | AC | 277 ms | 44352 KB |
subtask_1_30.txt | AC | 562 ms | 51944 KB |
subtask_1_31.txt | AC | 292 ms | 48152 KB |
subtask_1_32.txt | AC | 300 ms | 50324 KB |
subtask_1_33.txt | AC | 315 ms | 52264 KB |
subtask_1_34.txt | AC | 307 ms | 52140 KB |
subtask_1_35.txt | AC | 308 ms | 51344 KB |
subtask_1_36.txt | AC | 307 ms | 51588 KB |
subtask_1_37.txt | AC | 314 ms | 52256 KB |
subtask_1_38.txt | AC | 317 ms | 52140 KB |
subtask_1_39.txt | AC | 318 ms | 52608 KB |
subtask_1_40.txt | AC | 311 ms | 52220 KB |
subtask_1_41.txt | AC | 312 ms | 50724 KB |