Sơn Cọc Hàng Rào

Điểm: 1,00 (OI)

Giới hạn thời gian: 3.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Farmer John có $N$ con bò ( $1 \leq N \leq 10^{5}$ ) hàng ngày đi dạo quanh hàng rào bao quanh đồng cỏ. Hàng rào gồm $P$ cọc ( $4 \leq P \leq 2 \times 10^{5}$ , $P$ chẵn) tại các tọa độ 2D phân biệt. Các cọc nối với nhau bằng đoạn thẳng ngang hoặc dọc, tạo thành đa giác kín vuông góc.

Mỗi con bò đi từ vị trí bắt đầu đến vị trí kết thúc trên hàng rào theo hướng ngắn hơn. Một con bò chạm vào cọc nếu nó đi ngang qua cọc đó, hoặc cọc đó là điểm bắt đầu/kết thúc của nó.

Hãy đếm số lần mỗi cọc bị chạm.

Dữ liệu vào

Dòng 1: Hai số nguyên $N$ và $P$
$P$ dòng tiếp: Hai số nguyên $x$ , $y$ -- tọa độ mỗi cọc (không nhất thiết theo thứ tự quanh hàng rào)
$N$ dòng tiếp: Bốn số nguyên $x_{1}$ , $y_{1}$ , $x_{2}$ , $y_{2}$ -- vị trí bắt đầu và kết thúc

Dữ liệu ra

$P$ số nguyên, số thứ $i$ là số lần cọc thứ $i$ (theo thứ tự đầu vào) bị chạm.

Ràng buộc

$1 \leq N \leq 10^{5}$
$4 \leq P \leq 2 \times 10^{5}$ , $P$ chẵn
$0 \leq x, y \leq 10^{9}$
Giới hạn thời gian: 3s, bộ nhớ: 512MB
Test 4-6: $N, P \leq 1000$
Test 7-9: $0 \leq x, y \leq 1000$

Ví dụ

Input	Output	Giải thích
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	4 cọc tạo hình chữ nhật. 5 con bò đi trên hàng rào, mỗi cọc bị chạm số lần khác nhau.
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	8 cọc tạo đa giác phức tạp hơn.

Bình luận

Không có bình luận tại thời điểm này.