Hàng rào kỳ lạ (Khó)

Đ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 tùy ý (không chỉ nằm ngang/thẳng đứng) tạo thành các đa giác khép kín — mỗi hàng rào tiếp xúc đúng 2 hàng rào khác tại hai đầu mút. Có $C$ con bò không nằm trên hàng rào. Hai con bò cùng cộng đồng nếu đi được từ bò này đến bò kia không cắt qua hàng rà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 1000$ ).
$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. 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 1000$
Toạ độ trong $[0, 10^{6}]$
Mỗi đoạn hàng rào tiếp xúc đúng 2 đoạn khác tại hai đầu mút

Ví dụ

Input	Output	Giải thích
10 4 0 0 10 0 10 0 10 10 0 0 0 10 10 10 0 10 8 8 9 8 9 8 8 9 8 9 8 8 2 7 3 2 3 2 7 5 7 5 2 7 15 3 1 4 4 5 7 1	2	Có hình vuông lớn chứa tam giác nhỏ bên trong. Hai bò ngoài hình vuông cùng cộng đồng.

Bình luận

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