Đổi đất (bài 3 đề thi Olympic tin học Việt Nam)

Xem dạng PDF

Gửi bài giải

Điểm: 10,00 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M
Input: stdin
Output: stdout

Dạng bài

Hai bộ lạc Anpha và Bêta sống rất hòa thuận với nhau. Một phần ranh giới của hai bộ lạc là một đường gấp khúc không tự cắt. Đường gấp khúc nhận được bằng cách lần lượt nối N điểm đôi một khác nhau A1, A2,..., AN. Điểm Ai được xác định bởi hoành độ xi và tung độ yi (xi là các sô nguyên thỏa mãn điều kiện: xi ≤ x(i+1)). Phần đất của bộ lạc Anpha nằm ở phía trên đường gấp khúc.

Nhân dịp năm mới, tù trưởng hai bộ lạc quyết định thay đường ranh giới cũ bằng cách xây dựng một đường cao tốc đường nối thẳng từ A1 tới AN và lấy đường cao tốc này ranh giới mới. Dĩ nhiên, sự thay đổi này sẽ chuyển một phần đất của bộ lạc Anpha cho bộ lạc Bêta và ngược lại. Hai tù trưởng thỏa thuận phần diện tích chênh lệch do việc thay đường ranh giới sẽ được điều chỉnh trong tương lai bằng một cách khác.

Yêu cầu: Hãy tính diện tích phần đất SA của bộ lạc Anpha trở thành đất của bộ lạc Bêta và diện tích phần đất SB của bộ lạc Bêta trở thành đất của bộ lạc Anpha sau khi thay đổi đường ranh giới giữa hai bộ lạc.


Dữ liệu: Vào từ file văn bản LAND.INP trong đó:

Dòng đầu chứa số N(N ≤10000);

Dòng thứ i trong N dòng tiếp theo chứa hai số nguyên xi và yi đặt cách nhau ít nhất 1 dấu cách (-32000 ≤ xi, yi ≤ 32000).


Kết quả: Đưa ra file văn bản LAND.QUT trong đó dòng thứ nhất chứa SA, dòng thứ hai chứa SB.

Kết quả được lấy chính xác với 4 chữ số sau dấu chấm thập phân.


Input:
Copy
6
0   0
2   4
5   1
7   11
10  8
11  11
Output:
Copy
8.0000
9.0000

Bình luận

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.