Skip to content
Narrow screen resolution Wide screen resolution Auto adjust screen size Increase font size Decrease font size Default font size default color grey color
         
 | 
VNOI - Olympic tin học Việt Nam

Điểm tin VOJ

Số thành viên:6040
Số bài tập:1001
Số bài nộp:722923
Bài nộp hôm nay:0

Top 10 thành viên xuất sắc

HạngThành viênĐiểm
1mr_invincible587.9
2white_cobra418.6
3hieult403.4
4phaleq384.0
5vodanh9x368.2
6con_nha_ngheo352.0
7flash_mt350.2
8darksabers349.8
9yenthanh132345.3
10rockman9x_94343.1
Diễn đàn arrow Thư viện arrow Đề thi arrow IOI (thi quốc tế) arrow 2003 arrow Quan sát đường biên (seeing the boundary)
Quan sát đường biên (seeing the boundary) In E-mail
(0 votes)
Người viết: Ngô Minh Đức   
21/04/2008
Quan sát đường biên (seeing the boundary)

Ông nông dân Don quan sát hàng rào bao quanh cánh đồng phẳng hình vuông kích thước NxN (2 ≤N ≤ 500 000). Góc đầu tiên của hàng rào đặt tại tọa độ (0,0) góc đối diện có toạ độ (N,N); các cạnh bên là các đường thẳng song song với trục X và trục Y.



Các cọc rào được đặt ở 4 góc của khu đất và trên các cạnh bên cứ mỗi met có một cọc rào, tổng số cọc rào là 4xN. Các cọc rào được đặt thẳng đứng và coi như không có bán kính. Ông Don muốn xác định xem có thể quan sát được bao nhiêu cọc rào khi ông ta đứng ở một vị trí xác định phía bên trong hàng rào.

Khu đất của ông Don có R (1 ≤R≤30 000) tảng đá lớn làm che khuất tầm nhìn của ông đến một số cọc rào, bởi ông không đủ cao để nhìn qua được bất kỳ một tảng đá nào. Mỗi tảng đá là một đa giác lồi có diện tích khác 0 với tất cả các đỉnh có toạ độ nguyên.Các tảng đá được đặt hoàn toàn thẳng đứng. Các tảng đá không đặt chồng lên nhau, không chạm vào nhau, không chạm vào người ông Don và hàng rào. Ông Don cũng không đứng chạm hàng rào, không đứng trên tảng đá.

Cho kích thước của hàng rào, vị trí và hình dáng các tảng đá trong khu đất và vị trí của ông Don đứng, tính toán đưa ra số cọc rào mà ông ta nhìn thấy. Nếu như một đỉnh của tảng đá thẳng hàng với cọc rào từ vị trí ông Don thì cũng không thể nhìn thấy cọc rào đó.
Input: boundary.in
Dòng đầu tiên gồm hai số nguyên N và R cách nhau một dấu trắng.
Dòng tiếp theo gồm hai số nguyên X và Y là toạ độ của ông Don đứng phía bên trong hàng rào.
Những dòng còn lại miêu tả R tảng đá:
- Tảng đá thứ i được miêu tả bắt đầu bằng một số nguyên Pi (3 ≤Pi 20), là số đỉnh của tảng đá.
- Pi dòng tiếp theo gồm cặp số nguyên cách nhau bởi dấu trắng là toạ độ của các đỉnh. Toạ độ của các đỉnh là khác nhau và được cho theo thứ tự ngược chiều kim đồng hồ.

Ví dụ Input:
100 1
60 50
70 40
75 40
80 40
80 50
70 60
Chú ý tảng đá 1 có 3 đỉnh nằm trên một đường thẳng: (70,40), (75,40), và (80,40)
Output: boundary.out
Gồm một dòng duy nhất ghi một số nguyên là số cọc rào mà nông dân Don có thể quan sát được.
Ví dụ output:
319
Hạn chế
Thời gian chạy chương trình là 1 giây
Bộ nhớ 64MB
Cho điểm
Bạn sẽ nhận được điểm tối đa cho mỗi bộ test nếu chương trình của bạn đưa ra đúng file output. Các trường hợp còn lại không có điểm.

 
< Trước