a114. TOI 2025/12 潛力組：提拉米蘇

題目描述

有兩條從矩形左側通往右側的折線，將高度為 1 的長方體蛋糕切成三塊。每條折線以依序相連的整數座標頂點表示，第一個頂點的 x 座標是 0，最後一個頂點的 x 座標是蛋糕寬度；x 座標不遞減，因此允許垂直線段。

兩條折線不相交。請計算它們之間那塊蛋糕體積的兩倍。

輸入格式

第一行有 M、N，表示兩條折線的頂點數。第二行依序輸入第一條折線 M 個頂點的 x、y；第三行輸入第二條折線 N 個頂點的 x、y。

• 2 ≤ M、N ≤ 100000
• 0 ≤ x ≤ 10⁹，1 ≤ y ≤ 10⁹
• 兩條線的起點 x 都是 0，終點 x 相同，且符合上述條件。

輸出格式

輸出一個正整數，表示中間蛋糕體積的兩倍。

來源

TOI 2025 年 12 月潛力組〈提拉米蘇〉。本敘述重新撰寫；範例與測資為另行設計。 https://tpmso.k12ea.gov.tw/toi/wp-content/uploads/question/202512/Tiramisu.pdf