HCN2 - Khu vui chơi
Giới hạn- Thời gian: 0.511s
- 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.
Một mảnh đất được quy hoạch để làm khu vui chơi. Tuy nhiên mảnh đất lại không vuông vắn, trong khi khu vui chơi lại yêu cầu phải có dạng hình chữ nhật. Khuôn viên của mảnh đất được xác định bởi một đường gấp khúc khép kín không tự cắt với các hình chữ nhật có toạ độ nguyên trên hệ toạ độ vuông góc Đề-các Oxy.
Xác định trong khuôn viên mảnh đất hình chữ nhật có diện tích lớn nhất thoả mãn các điều kiện:
- Hình chữ nhật phải nằm hoàn toàn trong khuôn viên mảnh đất đã cho (nghĩa là hình chữ nhật không được chứa điểm nằm ngoài khuôn viên mảnh đất)
- Bốn đỉnh của hình chữ nhật phải có toạ độ nguyên
- Các cạnh phải song song với trục toạ độ Ox hoặc Oy
Input
- Dòng 1: N là số đỉnh của đường gấp khúc bao quanh mảnh đất. (N<=100)
- Dòng thứ i trong số N dòng tiếp theo chứa 2 số nguyên Xi, Yi (0<=Xi,Yi<=1000) được ghi cách nhau bởi 1 dấu cách. Các đỉnh của đường gấp khúc được đánh số từ 1 theo 1 chiều đi vòng quanh nó
Output
Gồm 1 dòng duy nhất chứa diện tích hình chữ nhật lớn nhất thoả mãn đề bài.
Example
Input: 7 0 5 2 7 3 5 4 9 6 5 5 0 0 0 Output: 25
các bạn có thắc mắc về đề bài hoặc test xin liên hệ quynh6174 qua forum vnoi.info
- Người up: huy391992