Trốn Tìm
Đề bài
Mô tả
Victor và Peter đang chơi trốn tìm. Peter đã trốn, còn Victor đứng yên tại chỗ và muốn biết liệu có thể nhìn thấy Peter hay không.
Trong phòng có đúng một bức tường mờ (không cho ánh sáng đi qua) và một tấm gương hai mặt. Victor là điểm có toạ độ , Peter là điểm . Tường là đoạn thẳng nối với , gương là đoạn thẳng nối với .
Quy tắc nhìn:
- Nếu một vật cản (tường hoặc gương) có điểm chung với đường ngắm, thì coi như hai người không thể nhìn thấy nhau qua đường ngắm đó.
- Nếu đường ngắm chạm vào gương, thì coi như xảy ra phản xạ: hai người nhìn thấy nhau qua gương. Phản xạ tuân theo định luật vật lý — góc tới bằng góc phản xạ, và tia tới cùng tia phản xạ phải nằm cùng một nửa mặt phẳng so với đường thẳng chứa gương. Nói cách khác, để nhìn thấy nhau qua gương, Victor và Peter phải nằm cùng phía so với đường thẳng chứa gương.
- Nếu đường ngắm song song với gương thì không xảy ra phản xạ, và gương không được coi là vật cản trong trường hợp này.
- Khi nhìn qua gương, đường đi của ánh sáng gồm hai đoạn (từ Victor tới điểm phản xạ trên gương, rồi từ điểm phản xạ tới Peter). Nếu một trong hai đoạn này bị tường chắn thì coi như không nhìn thấy.
Hãy xác định Victor có nhìn thấy Peter từ vị trí ban đầu hay không (trực tiếp hoặc qua gương).
Dữ liệu vào
- Dòng 1: hai số nguyên , — toạ độ Victor.
- Dòng 2: hai số nguyên , — toạ độ Peter.
- Dòng 3: bốn số nguyên — hai đầu của tường.
- Dòng 4: bốn số nguyên — hai đầu của gương.
Dữ liệu ra
In ra YES nếu Victor nhìn thấy Peter, ngược lại in ra NO.
Ràng buộc
- Tất cả các toạ độ là số nguyên có trị tuyệt đối không vượt quá .
- Hai đoạn thẳng (tường và gương) không có điểm chung.
- Victor và Peter không nằm trên bất kỳ đoạn thẳng nào.
- Toạ độ của Victor và Peter khác nhau.
- Các đoạn thẳng không suy biến thành điểm.
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 0 0 10 0 100 100 101 101 1 0 3 0 |
YES | Đường ngắm trực tiếp song song với gương nên gương không chắn; tường ở xa. |
| -1 3 1 3 0 2 0 4 0 0 0 1 |
NO | Đường ngắm trực tiếp bị tường chắn; Victor và Peter ở khác phía gương nên không thể phản xạ. |
| 0 0 1 1 0 1 1 0 -1 1 1 3 |
YES | Đường ngắm trực tiếp bị tường chắn, nhưng phản xạ qua gương cho ánh sáng từ Victor tới Peter mà không bị tường cản. |
| 0 0 2 0 1 1 1 -1 0 2 2 2 |
YES | Tường thẳng đứng chắn đường nhìn trực tiếp tại ; nhờ gương phía trên, phản xạ tại cho phép nhìn thấy nhau. |
Bình luận