bronze_Walking_Along_a_Fence (USACO US_Open_Contest)
Time limit: 2 seconds | Memory limit: 256 MB | Task type: batch
Algorithms: implementation, prefix sum

Farmer John's $N$ cows ($1 \leq N \leq 10^5$) each like to take a daily walk
around the fence enclosing his pasture.
The fence consists of $P$ posts ($4 \leq P \leq 2\cdot 10^5$, $P$ even), the
location of each being a different 2D point $(x,y)$ on a map of FJ's farm
($0 \leq x, y \leq 1000$).  Each post is connected to the two adjacent posts by
fences that are either vertical  or horizontal line segments, so the entire
fence can be considered a polygon whose sides are parallel to the x or y axes
(the last post connects back to the first post, ensuring the fence forms a
closed loop that encloses the pasture).  The fence polygon is "well-behaved" in
that fence segments only potentially overlap at their endpoints, each post
aligns with exactly  two fence segment endpoints, and every two fence segments
that meet at an endpoint are perpendicular.
Each cow has a preferred starting and ending position for her daily walk, each
being points somewhere along the fence (possibly at posts, possibly not).  Each
cow walks along the fence for her daily walks, starting from her starting
position and ending at her ending position.  There are two routes that the cow
could take, given that the fence forms a closed loop. Since cows are somewhat
lazy creatures, each cow will walk in the direction around the fence that is
shorter (if there is a tie, the cow may choose either direction).
Determine the distance that each cow walks.
INPUT FORMAT (input arrives from the terminal / stdin):
The first line of input contains $N$ and $P$. Each of the next $P$ lines
contains two integers representing the positions of the fence posts in clockwise
or counterclockwise order. Each of the next $N$ lines contains four integers
$x_1$ $y_1$ $x_2$ $y_2$ representing the starting position $(x_1, y_1)$ and
ending position $(x_2, y_2)$ of a cow.
OUTPUT FORMAT (print output to the terminal / stdout):
Write $N$ integers as output, giving the distance that each cow walks.
SAMPLE INPUT:
5 4
0 0
2 0
2 2
0 2
0 0 0 2
0 2 1 0
2 1 0 2
1 0 1 2
1 2 1 0
SAMPLE OUTPUT:
2
3
3
4
4
The first cow can walk directly from $(0,0)$ to $(0,2)$.
The second cow can walk from $(0,2)$ to $(0,0)$ and then to $(1,0)$.
The fourth cow has two possible routes with equal lengths:
$(1,0)\to (0,0)\to (0,2)\to (1,2)$ and $(1,0)\to (2,0)\to (2,2)\to (1,2)$.
SCORING:
Inputs 2-6: $0\le x,y \le 100$ and $N\le 100$
Inputs 7-11: No additional constraints.
Problem credits: Brian Dean

Starter code:

Grader code:

Setup script:

Evaluation script: