Strict Standards: call_user_func_array() expects parameter 1 to be a valid callback, non-static method HTML_content::show() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/includes/Cache/Lite/Function.php on line 98

Strict Standards: Non-static method HTML_content::_Itemid() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 452

Strict Standards: Non-static method HTML_content::_linkInfo() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 455

Strict Standards: Non-static method HTML_content::Title() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 470

Strict Standards: Non-static method HTML_content::PdfIcon() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 473

Strict Standards: Non-static method mosHTML::PrintIcon() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 476

Strict Standards: Non-static method mosAdminMenus::ImageCheck() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/includes/joomla.php on line 2329

Strict Standards: Non-static method HTML_content::EmailIcon() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 479
Quan sát đường biên (seeing the boundary)
Strict Standards: Non-static method HTML_content::EditIcon() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 632

Strict Standards: Non-static method HTML_content::Section_Category() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 511

Strict Standards: Non-static method HTML_content::Section() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 755

Strict Standards: Non-static method HTML_content::Category() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 758

Strict Standards: Non-static method HTML_content::Author() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 514

Strict Standards: Non-static method HTML_content::CreateDate() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 517

Strict Standards: Non-static method HTML_content::URL() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 520

Strict Standards: Non-static method HTML_content::ModifiedDate() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 536

Strict Standards: Non-static method HTML_content::ReadMore() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 539
Người viết: Ngô Minh Đức   
21/04/2008

Strict Standards: Non-static method HTML_content::TOC() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 526
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.

 
Strict Standards: Non-static method HTML_content::Navigation() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 550

Strict Standards: Non-static method mosHTML::CloseButton() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 553

Strict Standards: Non-static method mosHTML::BackButton() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 556