Sao chổi

View as PDF

Submit solution

Points: 0.83 (partial)
Time limit: 0.38s
Memory limit: 512M
Input: stdin
Output: stdout

Problem source:
VNOI Online 2011Tác giả: Khúc Anh Tuấn
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Năm ~2011~, cả thế giới háo hức chờ đợi sự xuất hiện của ngôi sao chổi VO11. Người dân ở khu vực miền núi phía bắc nước ta cũng không phải ngoại lệ, tất cả mọi người đều đang đứng ở trên các sườn núi để chờ đợi khoảnh khắc sao chổi xuất hiện. Tuy nhiên, các ngọn núi có thể che khuất tầm nhìn của một số người. Nhiệm vụ của bạn là đếm xem có bao nhiêu người may mắn nhìn thấy sao chổi.

Hình dung trên mặt phẳng tọa độ, ngôi sao chổi xuất hiện ở vị trí ~(0, Y_s)~ và ~d_i~ chuyển thẳng đến vị trí ~(0, Y_e)~ trước khi biến mất ~(Y_s < Y_e)~. Các sườn núi là một đường gấp khúc khi qua ~n~ điểm ~(x_1~, y1), ~(x_2~, y2), ..., (xn, yn), trong đó ~x_1 = 0 < x_2 < \dots < x_n~ và ~y_1 = 0 < y_2 > y_3 < \dots > y_n~. Có ~k~ người đang đứng ở trên sườn núi với tọa độ ~X~ lần lượt là ~p_1, p_2, \dots, p_k~ ~(p_1 < p_2 < \dots < p_k)~. Do những người này đang đứng trên sườn núi, bạn hoàn toàn có thể tính được tọa độ ~Y~ của từng người.

Bỏ qua chiều cao của mọi người, một người nhìn thấy sao chổi nếu ở một thời điểm nào đó, đoạn thẳng nối vị trí người này với vị trí sao chổi không cắt bất cứ sườn núi nào. Một đoạn thẳng nằm trên biên của một sườn núi không được tính là cắt sườn núi đó.

Input

  • Dòng đầu ghi hai số ~N~, ~K~. ~(N \le 50000~, ~K \le 50000~, ~N~ lẻ)
  • Dòng sau ghi hai số ~Y_s~, ~Y_e~.
  • Trong ~N~ dòng sau, dòng thứ ~i~ ghi ~2~ số ~x_i~, ~y_i~.
  • Dòng cuối ghi ~K~ số ~p_1~, ~p_2~, ...~p_k~.
  • Tất cả các tọa độ đều là số tự nhiên không vượt quá ~1000000~.

Output

  • Số người có thể nhìn thấy sao chổi.

Giới hạn

  • ~50\%~ số test có ~N~, ~K \le 10~, trong đó, ~20\%~ số test có ~N = 3~.

Sample Input

3 2
1 2
0 0
2 2
3 0
1 3

Sample Output

1

Comments

Please read the guidelines before commenting.


There are no comments at the moment.