VO 15 Bài 4 - Chuyện mưa

View as PDF

Submit solution

Points: 1.57 (partial)
Time limit: 4.5s
Memory limit: 256M
Input: stdin
Output: stdout

Problem source:
VO 2015
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

"Mưa từng con phố có nhớ bóng dáng em đi cuối thu, đông về hè sang vội
vàng quá

Mưa từng đêm vắng, mưa ơi cứ rơi phố xa, anh đi tìm yêu đương chiều
qua

Ai vội vàng đi ngang lòng người mang theo bao yêu đương thoáng qua như
là cơn mưa rào

Chuyện mưa"

Có bao giờ bạn tự hỏi, những giọt mưa kia rồi sẽ về đâu? Chúng ta hãy cùng nhau trả lời câu hỏi này nhé.

Hình dung thế giới như một mặt phẳng ~\left(Oxy\right)~, tại mỗi thời điểm có ~1~ trong ~3~ loại sự kiện xảy ra:

  • Một đoạn thẳng nối điểm ~\left(x_1, y_1\right)~ và ~\left(x_2, y_2\right)~ xuất hiện trên mặt phẳng.
  • Một đoạn thẳng được thêm vào trước đó biến mất.
  • Một giọt mưa xuất hiện tại điểm ~\left(x, y\right)~ và rơi xuống. Giọt mưa rơi theo phương thẳng đứng từ điểm ~\left(x, y\right)~ về điểm ~\left(x, 0\right)~.

Nhiệm vụ của bạn là xác định xem, giọt mưa rơi xuống mặt đất, hay rơi vào một đoạn thẳng.

Input

Dòng đầu chứa số nguyên dương ~Q~ ~\left(Q \leq 10^5\right)~, cho biết số sự kiện xảy ra.

~Q~ dòng tiếp theo, mỗi dòng cho biết ~1~ sự kiện xảy ra. Mỗi dòng có ~1~ trong ~3~ dạng:

  • 1 ~x_{1}~ ~y_{1}~ ~x_{2}~ ~y_{2}~ : Một đoạn thẳng xuất hiện, nối điểm ~\left(x_1, y_1\right)~ và ~\left(x_2, y_{2}\right)~. ~\left(1 \leq x_1, y_1, x_2, y_2 \leq 10^6;\text{ } x_1 \ne x_2\right)~. Không có ~2~ đoạn thẳng nào có điểm chung.
  • 2 ~i~: Đoạn thẳng xuất hiện thứ ~i~ (tính cả những đoạn đã bị xóa) biến mất ~\left(1 \leq i \leq \text{số đoạn thẳng đã xuất hiện}\right)~. Nếu đoạn thẳng thứ ~i~ đã biến mất trước đó, sự kiện này không có bất kỳ ảnh hưởng gì.
  • ~3 \text{ } x \text{ } y~: Một giọt mưa xuất hiện ở tọa độ ~\left(x, y\right)~. ~\left(1 \leq x, y \leq 10^6\right)~. Chú ý rằng giọt mưa có thể nằm trên đoạn thẳng.

Output

Với mỗi sự kiện loại ~3~, in ra ~0~ nếu giọt mưa sẽ rơi xuống đất mà không chạm vào bất kỳ đoạn thẳng nào. Ngược lại, in ra thứ tự của đoạn thẳng đầu tiên mà giọt mưa chạm vào.

Giới hạn

  • Trong ~30\%~ test đầu tiên: ~Q \leq 10^3~ .
  • Trong ~30\%~ test tiếp theo, trong các sự kiện loại ~1~: ~1 \leq x_1, y_1, x_2, y_2 < 10^6~. Trong các sự kiện loại ~3~: ~y = 10^6~ .
  • Các test còn lại không có ràng buộc gì thêm.
  • Mọi giá trị ~x, y~ đều là số nguyên.

Sample Input

12
1 1 2 3 2
3 1 1
3 2 1
3 3 1
3 1 2
3 2 2
3 3 2
3 1 3
3 2 3
3 3 3
2 1
3 2 2

Sample Output

0
0
0
1
1
1
1
1
1
0

Comments

Please read the guidelines before commenting.


There are no comments at the moment.