페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#8172
서브태스크

Painting Fence Posts 1s 1024MB

문제

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.


입력

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.


부분문제

번호 점수 조건
#120점

N, P \le 1000

#230점

All locations satisfy 0≤x,y≤1000

#350점

추가 제약 조건 없음


예제 #1

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 3
1
2
2
1

The 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:

  1. Posts 2 and 4.

  2. Posts 2 and 3.

  3. Posts 1 and 3.

  4. No posts.

  5. No posts.


예제 #2

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 3
1
0
0
0
1
1
1
2

예제 #3

1 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 2
1
1
1
1
1
0
0
0
0
0
0
0


출처

USACO 2024 US Open Silver

로그인해야 코드를 작성할 수 있어요.