Dây thừng và hàng rào

Điểm: 1,00 (OI)

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

Có $N$ cọc hàng rào tại cùng một tọa độ $x$ (tọa độ $x$ của cọc nhỏ hơn tọa độ $x$ của bò). Một sợi dây gồm $M + 1$ điểm tạo thành vòng kín bắt đầu và kết thúc tại vị trí của bò. Không có cọc nào nằm trên đoạn thẳng của dây.

Tìm số cọc tối thiểu cần phá bỏ để bò có thể chạy thoát về phía $x = + \infty$ mà dây không bị kéo căng.

Dữ liệu vào

Dòng $1$ : Bốn số nguyên $N$ , $M$ , $b x$ , $b y$ — số cọc, số đoạn dây, tọa độ bò.
$N$ dòng tiếp: Tọa độ $(x, y)$ của cọc.
$M + 1$ dòng tiếp: Tọa độ $(x, y)$ của các điểm trên dây (đầu và cuối bằng vị trí bò).

Dữ liệu ra

Một số nguyên — số cọc tối thiểu cần xóa.

Ràng buộc

$1 \leq N \leq 10$
$1 \leq M \leq 10000$

Ví dụ

Input	Output	Giải thích
2 10 6 1 2 3 2 1 6 1 2 4 1 1 2 0 3 1 1 3 5 4 3 0 0 1 3 2 6 1	1	Phá bỏ 1 trong 2 cọc là đủ.
1 5 101 100 100 100 101 100 99 101 99 99 99 101 101 100	0	Bò đã tự do, không cần phá cọc.

Bình luận

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