2. Google Code Jam 2011 - Irregular Cakes
Mary là một nhà toán học và cô có một tiệm bánh được thành lập cách đây vài năm. Sau ngần ấy thời gian, cô cảm thấy nhàm chán với việc luôn nướng những chiếc bánh hình chữ nhật và hình tròn giống nhau. Cho sinh nhật sắp tới, cô muốn nướng một chiếc bánh bất quy tắc (irregular cake), được định nghĩa là phần diện tích nằm giữa hai "đường gấp khúc" (polylines) từ \(x=0\) đến \(x=W\). Những đường gấp khúc này được gọi là biên dưới và biên trên.
Về mặt hình học, một đường gấp khúc được định nghĩa bởi một chuỗi các điểm \((P_0, P_1, \dots, P_n)\) đi từ trái sang phải. Các điểm liên tiếp được nối với nhau tạo thành một chuỗi các đoạn thẳng, cùng nhau tạo nên đường gấp khúc.
Hôm nay là sinh nhật của Mary và cô đã nướng một chiếc bánh bất quy tắc được giới hạn bởi hai đường gấp khúc có lần lượt \(L\) điểm và \(U\) điểm. Sau khi hát bài "Chúc mừng sinh nhật", cô muốn thực hiện \(G-1\) nhát cắt thẳng đứng để chia chiếc bánh thành \(G\) phần có diện tích bằng nhau. Sau đó, cô có thể chia sẻ các phần bánh này cho tất cả khách mời của mình. Tuy nhiên, hình dạng bất quy tắc của chiếc bánh khiến nhiệm vụ này khá khó khăn. Bạn có thể giúp cô ấy quyết định vị trí các nhát cắt không?
Dữ liệu vào
Dòng đầu tiên của dữ liệu vào cho biết số lượng bộ test, \(T\). Tiếp theo là \(T\) bộ test. Mỗi bộ test bắt đầu bằng một dòng chứa bốn số nguyên: \(W\) (chiều rộng của bánh), \(L\) (số điểm trên biên dưới), \(U\) (số điểm trên biên trên) và \(G\) (số lượng khách mời tại bữa tiệc).
Tiếp theo là \(L\) dòng xác định biên dưới. Dòng thứ \(i\) chứa hai số nguyên \(x_i\) và \(y_i\), đại diện cho tọa độ của điểm thứ \(i\) trên biên dưới. Tiếp theo là \(U\) dòng nữa xác định biên trên. Dòng thứ \(j\) ở đây chứa hai số nguyên \(x_j\) và \(y_j\), đại diện cho tọa độ của điểm thứ \(j\) trên biên trên.
Dữ liệu ra
Đối với mỗi bộ test, hãy xuất ra \(G\) dòng. Dòng đầu tiên phải là Case #x:, trong đó \(x\) là số thứ tự bộ test (bắt đầu từ 1). \(G-1\) dòng tiếp theo phải chứa tọa độ \(x\) nơi các nhát cắt phải được thực hiện, được sắp xếp từ nhát cắt bên trái nhất đến nhát cắt bên phải nhất.
Các câu trả lời có sai số tương đối hoặc tuyệt đối không quá \(10^{-6}\) sẽ được coi là chính xác.
Ràng buộc
- \(1 \le T \le 100\).
- \(1 \le W \le 1000\).
- \(2 \le L \le 100\).
- \(2 \le U \le 100\).
- Tất cả các tọa độ sẽ là các số nguyên nằm trong khoảng từ \(-1000\) đến \(1000\), bao gồm cả hai đầu mút.
- Tọa độ \(x\) của điểm ngoài cùng bên trái của cả hai biên sẽ là \(0\).
- Tọa độ \(x\) của điểm ngoài cùng bên phải của cả hai biên sẽ là \(W\).
- Các điểm trong cùng một biên sẽ được sắp xếp tăng dần theo tọa độ \(x\).
- Các điểm trong cùng một biên sẽ có tọa độ \(x\) khác nhau.
- Biên dưới sẽ luôn nằm hoàn toàn bên dưới biên trên đối với mọi \(x\) từ \(0\) đến \(W\), bao gồm cả hai đầu mút. (Nói cách khác, biên dưới sẽ có tọa độ \(y\) nhỏ hơn biên trên tại mọi vị trí \(x\).)
Phân nhóm
- Test set 1 (Visible): \(2 \le G \le 3\).
- Test set 2 (Hidden): \(2 \le G \le 101\).
Điểm các phân nhóm
Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.
| Phân nhóm | Điểm Google Code Jam | Tỷ lệ điểm của bài |
|---|---|---|
| Test Set 1 | 7/14 | 50% |
| Test Set 2 | 7/14 | 50% |
Ví dụ
Ví dụ 1
Input
2
15 3 3 3
0 6
10 8
15 9
0 10
5 11
15 13
8 3 4 2
0 2
5 4
8 3
0 5
3 4
4 7
8 5Output
Case #1:
5.000000
10.000000
Case #2:
4.290588Nguồn
Google Code Jam 2011, Vòng 3, bài Irregular Cakes.
Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.
