Gương Phản Chiếu

Đ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$ gương phẳng đặt tại các vị trí nguyên trên mặt phẳng tọa độ. Mỗi gương nằm ở vị trí $(x_{i}, y_{i})$ và có hướng là "/" hoặc "\" (nghiêng 45 độ). Một tia sáng xuất phát từ điểm $(0, 0)$ theo hướng sang phải (hướng Đông). Khi gặp gương, tia sáng phản chiếu theo quy tắc:

Gương "/": Tia từ Đông → Bắc, từ Tây → Nam, từ Bắc → Đông, từ Nam → Tây
Gương "\": Tia từ Đông → Nam, từ Tây → Bắc, từ Bắc → Tây, từ Nam → Đông

Mục tiêu là tia sáng cần đến điểm $(a, b)$ . Biết rằng chính xác một gương có thể đang đặt sai hướng (hoặc tất cả đều đúng). Hãy tìm chỉ số của gương cần đổi hướng (từ "/" thành "\" hoặc ngược lại) để tia sáng đến được $(a, b)$ .

Dữ liệu vào

Dòng 1: Ba số nguyên $N$ , $a$ , $b$
Dòng $2$ đến $N + 1$ : Mỗi dòng gồm $x_{i}$ , $y_{i}$ và ký tự "/" hoặc "\" mô tả gương thứ $i$

Dữ liệu ra

In ra chỉ số (1-indexed) của gương cần đổi hướng
In ra $0$ nếu tia sáng đã đến đích mà không cần thay đổi gương nào
In ra $- 1$ nếu không thể đạt được dù thay đổi bất kỳ một gương nào

Ràng buộc

$1 \leq N \leq 200$
$- 10^{6} \leq x_{i}, y_{i}, a, b \leq 10^{6}$
Không có gương nào tại $(0, 0)$ hoặc $(a, b)$

Ví dụ

Input	Output	Giải thích
5 6 2 3 0 / 0 2 / 1 2 / 3 2 <br>1 3 \	4	Đổi gương 4 từ "\" thành "/" thì tia sáng đến được (6,2)
6 4 -2 2 0 / 2 2 <br>4 2 <br>2 -2 <br>-2 2 / -2 0 \	1	Đổi gương 1 từ "/" thành "\" thì tia sáng đến được (4,-2)

Ghi chú

Tia sáng đi theo đường thẳng giữa các gương. Nếu tia sáng ra khỏi giới hạn tọa độ hoặc đi vào vòng lặp vô hạn mà không đến đích thì coi là thất bại.

Bình luận

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