Rào Đàn Bò (Gold)

Điểm: 1,00 (OI)

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

Cho $N$ con bò tại các tọa độ nguyên và $Q$ truy vấn. Mỗi truy vấn là một trong hai loại:

Loại 1 (1 x y): Thêm con bò mới tại tọa độ $(x, y)$ .
Loại 2 (2 A B C): Kiểm tra xem hàng rào $A x + B y = C$ có "dùng được" không — tức là tất cả các con bò hiện tại đều nằm cùng một phía (không có con nào nằm đúng trên hàng rào).

Với mỗi truy vấn loại 2, in ra YES hoặc NO.

Với mỗi truy vấn loại 2, in YES hoặc NO trên một dòng.

$1 \leq N, Q \leq 10^{5}$
$| x |, | y | \leq 10^{9}$
$| A |, | B | \leq 10^{9}$ , $| C | \leq 10^{18}$ , $A$ và $B$ không đồng thời bằng 0

Input	Output	Giải thích
3 4 0 0 0 1 1 0 2 2 2 3 1 1 1 2 2 2 3 2 0 1 1	YES NO NO	Ban đầu max(2x+2y)=2<3 → YES. Thêm (1,1): max=4≥3, min=0≤3 → NO. y=1: có bò nằm trên hàng rào → NO

Bình luận

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