Cân bằng cần cẩu
Đề bài
Mô tả
Ở đâu có công trình xây dựng lớn, ở đó có những chiếc cần cẩu làm công việc nâng hạ. Hiếm ai nghĩ tới việc cần cẩu là những ví dụ tuyệt vời của kỹ thuật: một kết cấu có trọng lượng (tương đối) nhỏ nhưng nâng được những vật nặng hơn nhiều. Tuy vậy, ngay cả những chiếc cần cẩu được chế tạo tốt nhất cũng có giới hạn về khối lượng mà chúng nâng được.
Hiệp hội các nhà sản xuất cần cẩu (ACM) cần một chương trình tính khoảng khối lượng mà một cần cẩu có thể nâng. Vì cần cẩu có tính đối xứng, các kỹ sư của ACM quyết định chỉ xét một mặt cắt ngang của cần cẩu, có thể xem như một đa giác đặt trên trục .

Hình: mặt cắt ngang của cần cẩu trong ví dụ thứ nhất. Mũi tên chỉ đỉnh treo vật nặng.
Hình trên là mặt cắt ngang của cần cẩu trong ví dụ thứ nhất. Giả sử mỗi ô của mặt cắt ngang cần cẩu nặng kilôgam (khối lượng phân bố đều, khối lượng cần cẩu bằng diện tích đa giác), và vật cần nâng được treo tại một đỉnh của đa giác (đỉnh mà mũi tên chỉ vào trong hình). Hãy viết chương trình xác định khoảng khối lượng vật nặng mà với nó cần cẩu không bị đổ sang trái hay sang phải.
Cần cẩu chỉ tựa lên mặt đất tại các đỉnh của đa giác nằm trên trục . Cần cẩu không đổ khi và chỉ khi hoành độ trọng tâm chung của cần cẩu và vật nặng nằm trong đoạn từ hoành độ nhỏ nhất tới hoành độ lớn nhất của các điểm tựa đó (kể cả hai đầu mút).
Dữ liệu vào
Dòng đầu tiên chứa một số nguyên , số đỉnh của đa giác mô tả hình dạng cần cẩu.
dòng tiếp theo, mỗi dòng chứa hai số nguyên , : tọa độ các đỉnh của đa giác theo thứ tự. Vật nặng được treo tại đỉnh đầu tiên của đa giác.
Dữ liệu ra
In ra khoảng khối lượng (tính bằng kilôgam) có thể treo vào cần cẩu mà cần cẩu không bị đổ. Nếu khoảng đó là , in ra .. . Ví dụ, nếu khoảng là , in ra 1 .. 14. Nếu khoảng là , in ra .. inf. Nếu cần cẩu không thể mang bất kỳ khối lượng nào, in ra unstable.
Ràng buộc
- .
- , .
- Đa giác là đa giác đơn, có ít nhất hai đỉnh nằm trên trục .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 7 50 50 0 50 0 0 30 0 30 30 40 40 50 40 |
0 .. 1017 | Đây là cần cẩu trong hình. Các điểm tựa là và , vật treo tại . |
| 7 50 50 0 50 0 0 10 0 10 30 20 40 50 40 |
unstable | Các điểm tựa là và : trọng tâm cần cẩu đã nằm bên phải ngay cả khi không treo gì, và treo thêm ở chỉ làm nó lệch phải thêm. |
Bình luận