Cắt Cỏ

Điểm: 1,00 (OI)

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

Một máy cắt cỏ di chuyển trên mặt phẳng theo $N$ đoạn thẳng liên tiếp, luân phiên nằm ngang và thẳng đứng. Bạn được cho tọa độ của $N + 1$ điểm (bao gồm điểm xuất phát), tạo thành $N$ đoạn (đánh số từ $0$ đến $N - 1$ ).

Đoạn thứ $i$ và đoạn thứ $j$ ( $i < j$ ) giao nhau vuông góc nếu:

Một đoạn nằm ngang và đoạn kia thẳng đứng,
Chúng thực sự cắt nhau (không chỉ chạm đầu mút),
$j - i \geq T$ .

Đếm số cặp đoạn giao nhau vuông góc thỏa mãn điều kiện trên.

Dữ liệu vào

Dòng đầu: hai số nguyên $N$ và $T$ (số điểm và ngưỡng khoảng cách).
$N$ dòng tiếp theo: mỗi dòng chứa hai số nguyên $x_{i}$ , $y_{i}$ là tọa độ của điểm thứ $i$ (từ $0$ đến $N - 1$ ).

Đảm bảo: Các đoạn liên tiếp luân phiên nằm ngang và thẳng đứng (tức là mỗi đoạn chỉ thay đổi đúng một tọa độ so với đoạn trước).

Dữ liệu ra

Một số nguyên duy nhất — số cặp đoạn giao nhau vuông góc với $j - i \geq T$ .

Ràng buộc

$2 \leq N \leq 10^{5}$
$0 \leq x_{i}, y_{i} \leq 10^{9}$
$2 \leq T \leq N$ ( $T$ là số chẵn)

Ví dụ

Input	Output	Giải thích
7 4 0 10 10 10 10 5 3 5 3 12 6 12 6 3	1	Đoạn 5 (thẳng đứng, $x = 6$ , $y \in [3, 12]$ ) giao với đoạn 0 (nằm ngang, $y = 10$ , $x \in [0, 10]$ ) với $5 - 0 = 5 \geq 4$ . Đây là cặp duy nhất thỏa mãn.

Ghi chú

Hai đoạn được coi là giao nhau khi chúng cắt nhau tại một điểm nằm hoàn toàn bên trong cả hai đoạn (không phải tại đầu mút).
$T$ luôn là số chẵn.

Bình luận

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