Bus Stops (APCS 2022-10 Beginner)

Points 100 1.0s 256M

There are \(n\) bus stops on a plane; the \(i\)-th stop is at coordinates \((x_i, y_i)\).

The travel time between two stops is the Manhattan distance between their coordinates. For two points \((x_1, y_1)\) and \((x_2, y_2)\), the Manhattan distance is \(|x_1 - x_2| + |y_1 - y_2|\).

Today you ride from stop \(1\) to stop \(n\), passing through stops \(2, 3, 4, \ldots, (n-1)\) in order. Compute the maximum and minimum travel time between consecutive stops along the way.

Input

The first line contains a positive integer \(n\), the number of stops along the route.

Lines \(2\) through \(n+1\) each contain two integers, the coordinates of a stop: line \(i+1\) contains \(x_i\) and \(y_i\).

Constraints

  • \(4 \le n \le 100\)
  • \(-100 \le x_i, y_i \le 100\)

Output

Output two integers on one line separated by a space: the maximum travel time between consecutive stops, then the minimum.

Scoring

The time limit for each test case is \(1\) second; your score is the sum over the test cases you pass. The subtasks are:

  • Subtask 1 (\(60\) points): \(n = 4\) and \(-100 \le x_i, y_i \le 100\).
  • Subtask 2 (\(40\) points): \(4 \le n \le 100\) and \(-100 \le x_i, y_i \le 100\).

Sample Input 1

4
1 1
1 3
4 5
2 6

Sample Output 1

5 2

Sample Input 2

4
1 2
-1 -1
1 3
0 0

Sample Output 2

6 4

Source

APCS programming exam, October 2022, Problem 1.

Problem page help

Keyboard shortcuts

Main features

  • Sample tests — Runs the sample cases bundled with the problem and auto-compares against the expected output.
  • Custom test — Run your code with your own stdin. Optionally tick the "Compare with expected (diff)" box to verify against expected output line-by-line.
  • Template — Paste the default code template you set on your profile page.
  • Collab — Edit this problem together with classmates in real time.
  • Auto-draft — Editor contents auto-save to your browser every 1.5 seconds (per account / problem / language).
  • Submit — Send your code to the judge for grading; returns AC / WA / TLE etc.

Limits

  • Source code: at most 65,536 characters
  • Custom test stdin and expected output: at most 1 MB each (≈1 million characters)
  • Custom test and sample test share the sandbox; about 1 request per 3 s per user (sample test: 1 per 1 s)
  • Custom test and sample test both have a 15 second wall-clock cap (the official judge still uses the problem time limit)
  • Interactive problems do not offer custom test (cannot simulate interaction with the judge).
  • Submitting has no rate limit, but rapid repeated submissions on the same problem are treated as score farming.