Hàng rào kỳ lạ (Dễ)

Điểm: 1,00 (OI)

Giới hạn thời gian: 2.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

Có $N$ đoạn hàng rào nằm ngang hoặc thẳng đứng trên mặt phẳng tọa độ. Các hàng rào chỉ tiếp xúc nhau tại đầu mút. Có $C$ con bò, mỗi con đứng tại một điểm không nằm trên hàng rào nào. Hai con bò thuộc cùng một cộng đồng nếu có thể đi từ bò này đến bò kia mà không cắt qua hàng rào nào.

Tìm kích thước cộng đồng lớn nhất.

Dữ liệu vào

Dòng $1$ : Hai số nguyên $N$ và $C$ ( $1 \leq N, C \leq 500$ ).
$N$ dòng tiếp: Bốn số nguyên $x_{1}, y_{1}, x_{2}, y_{2}$ mô tả một đoạn hàng rào (nằm ngang hoặc thẳng đứng). Toạ độ trong $[0, 10^{6}]$ .
$C$ dòng tiếp: Hai số nguyên $x, y$ — vị trí mỗi con bò.

Dữ liệu ra

Một số nguyên — số bò trong cộng đồng lớn nhất.

Ràng buộc

$1 \leq N, C \leq 500$
Toạ độ trong $[0, 10^{6}]$

Ví dụ

Input	Output	Giải thích
7 3 0 0 10 0 10 0 10 5 12 5 10 5 10 5 1 5 12 5 12 7 0 7 12 7 0 7 0 0 3 4 6 6 17 3	2	Bò 1 và bò 2 cùng cộng đồng. Bò 3 bị ngăn cách.

Bình luận

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