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
AC × 3
AC × 47
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