Đèn pha chiếu sáng

Xem dưới dạng PDF

Gửi bài giải


Điểm: 20
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M
đầu vào: stdin
Đầu ra: stdout

Tác giả:
Kiểu bài tập

An đang thiết kế một đèn pha chiếu sáng đặt tại gốc toạ độ. Đèn pha có góc chiếu sáng là \(\alpha\) độ. An có thể xoay đèn pha tuỳ ý quanh gốc. Có \(n\) điểm trên mặt phẳng cần được chiếu sáng. An muốn biết số điểm tối đa có thể chiếu sáng đồng thời.

Một điểm được chiếu sáng nếu góc cực của nó nằm trong góc quét của đèn pha (tính cả hai biên).

Định dạng đầu vào

  • Dòng đầu chứa hai số nguyên \(n\) (\(1 \le n \le 10^5\)) và số thực \(\alpha\) (\(0 < \alpha \le 360\)).
  • \(n\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(x_i, y_i\) (\(|x_i|, |y_i| \le 10^6\)). Không có điểm nào trùng với gốc toạ độ.

Định dạng đầu ra

  • Một số nguyên duy nhất là số điểm tối đa có thể chiếu sáng.

Ví dụ

Input:

5 90
1 0
0 1
-1 0
0 -1
1 1

Output:

3

Giải thích: Với góc chiếu sáng \(90^\circ\), xoay đèn pha để chiếu vào ba điểm \((1,0), (1,1), (0,1)\) là tối đa.

Ràng buộc

  • Subtask 1 (20 điểm): \(n \le 100\).
  • Subtask 2 (30 điểm): \(n \le 10^4\).
  • Subtask 3 (50 điểm): \(n \le 10^5\).

Nhận xét

Không có ý kiến tại thời điểm này.