Painting Fence Posts
실버 II의견: 0
*Note: The time limit and memory limit for this problem are 3s and 512MB, which are
1.5x and 2x the normal amount, respectively.*
Farmer John's \(N\) cows (\(1 \leq N \leq 10^5\)) each like to take a daily walk
around the fence enclosing his pasture. Unfortunately, whenever a cow walks
past a fence post, she brushes up against it, requiring Farmer John to need to
repaint the fence posts regularly.
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 10^9\)). 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. Remarkably, this choice is always clear -- there are no ties!
A cow touches a fence post if she walks past it, or if the fence post is the
starting or ending point of her walk. Please help FJ calculate the number of
daily touches experienced by each fence post, so he knows which post to repaint
next.
It can be shown that there is exactly one possibility for the fences given the
locations of all of the posts.
Problem credits: Brian Dean
SCORING
- Inputs 4-6: \(N,P\le 1000\)
- Inputs 7-9: All locations satisfy \(0\le x, y\le 1000\).
- Inputs 10-15: No additional constraints.
Problem credits: Brian Dean
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 no
particular 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.
Write \(P\) integers as output, giving the number of touches experienced by each
fence post.
5 4
3 1
1 5
3 5
1 1
2 1 1 5
1 5 3 4
3 1 3 5
2 1 2 1
3 2 3 31
2
2
1The following posts are connected by fence segments:
$$ (3,1)\leftrightarrow (3, 5) \leftrightarrow (1,5) \leftrightarrow (1,1) \leftrightarrow (3,1) $$
The posts touched by each cow are as follows:
- Posts \(2\) and \(4\).
- Posts \(2\) and \(3\).
- Posts \(1\) and \(3\).
- No posts.
- No posts.
2 8
1 1
1 2
0 2
0 3
0 0
0 1
2 3
2 0
1 1 2 1
1 0 1 31
0
0
0
1
1
1
21 12
0 0
2 0
2 1
1 1
1 2
3 2
3 3
1 3
1 4
2 4
2 5
0 5
2 2 0 21
1
1
1
1
0
0
0
0
0
0
0riseoj 작성
출처 올림피아드 > USACO > 2023-2024 > US Open > Silver
평가 및 의견
Painting Fence Posts
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Painting Fence Posts