POLY4 - Sao đa giác
Giới hạn- Thời gian: 0.116s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
Cho các đa giác không tự cắt, một đa giác được gọi là đa giác hình sao nếu như tồn tại một điểm nằm trong đa giác mà từ điểm đó có thể nhìn thấy tất cả các điểm nằm trong đa giác đó.
Hai điểm là nhìn thấy nhau có nghĩa là khi nối chúng thì tạo thành 1 đoạn thẳng không cắt bất cứ một cạnh nào của đa giác.
Hãy kiểm tra xem đa giác có phải là đa giác hình sao không?.
Input
Gồm một số test, mỗi test dòng đầu là n (n <= 50) (số đỉnh của đa giác).
Tiếp theo là n cặp số nguyên x, y (-10000 <= x, y <= 10000) mô tả tọa độ của các đỉnh đi theo một chiều nhất định (ngược hoặc thuận chiều kim đồng hồ).
Kết thúc test là số 0
Output
Ghi ra 1 hay 0 trên một dòng tương ứng nếu đa giác là hình sao hoặc không là hình sao.
Example
Input: 3 0 0 0 1 1 1 6 66 13 96 61 76 98 13 94 4 0 45 68 8 27 21 55 14 93 12 56 95 15 48 38 46 51 65 64 31 0 Output: 1 1 0
- Người up: dtmp