a074.
TOI2011 第五題：畫作問題
內容
有一個現代藝術創作者，他的作品主要是以線條將空間分割成一些幾何圖形區域，再對各幾何圖形區域進行著色。
他特別創造了一系列的作品--直線與 45 度角的對話，這些作品以系統化的方式繪製，皆可以精準地重複以手工複製。
其製作方法如下：先取一張長與寬為整數單位長度的矩形紙，在邊上畫出單位刻度；
再將矩形紙輕描出以單位長度為基準的方格，則畫紙將形成一張方格紙。
接下來以畫紙的左下角當作原點，只要指定兩個座標點連起來，即形成畫紙上的一條直線。
此系列畫作的特色如下：
1. 只有水平直線、垂直直線、以及和矩形紙邊成 45 度角的直線。
2. 直線的兩端一定落在矩形紙邊上。
3. 畫紙上被這些直線所分割出來的三角形一定採用不同的顏色。
請你寫一個程式根據創作者所給定直線的端點，計算出圖形中所分割
出的三角形個數，以決定需要採用幾種顏色。
舉例說明如下：取一張 4×4 單位長度的矩形紙如圖一：
圖一
其水平邊及垂直邊皆為 4 單位長度，畫上去的四條直線的端點分別為
Line 1: (0, 0), (4, 4)
Line 2: (0, 2), (4, 2)
Line 3: (0, 2), (2, 4)
Line 4: (1, 4), (4, 1)
其中分割出的三角形個數為 4。
若取一張 4×6 單位長度的矩形紙如圖二，
圖二
其水平邊為 4 單位長度，垂直邊為 6 單位長度，畫上去的六條直線的端點分別為
Line 1: (0, 1), (4, 5)
Line 2: (0, 3), (4, 3)
Line 3: (0, 4), (4, 4)
Line 4: (0, 3), (3, 6)
Line 5: (0, 5), (4, 1)
Line 6: (1, 6), (4, 3)
其中分割出的三角形個數為 11。
他特別創造了一系列的作品--直線與 45 度角的對話，這些作品以系統化的方式繪製，皆可以精準地重複以手工複製。
其製作方法如下：先取一張長與寬為整數單位長度的矩形紙，在邊上畫出單位刻度；
再將矩形紙輕描出以單位長度為基準的方格，則畫紙將形成一張方格紙。
接下來以畫紙的左下角當作原點，只要指定兩個座標點連起來，即形成畫紙上的一條直線。
此系列畫作的特色如下：
1. 只有水平直線、垂直直線、以及和矩形紙邊成 45 度角的直線。
2. 直線的兩端一定落在矩形紙邊上。
3. 畫紙上被這些直線所分割出來的三角形一定採用不同的顏色。
請你寫一個程式根據創作者所給定直線的端點，計算出圖形中所分割
出的三角形個數，以決定需要採用幾種顏色。
舉例說明如下：取一張 4×4 單位長度的矩形紙如圖一：
圖一
其水平邊及垂直邊皆為 4 單位長度，畫上去的四條直線的端點分別為
Line 1: (0, 0), (4, 4)
Line 2: (0, 2), (4, 2)
Line 3: (0, 2), (2, 4)
Line 4: (1, 4), (4, 1)
其中分割出的三角形個數為 4。
若取一張 4×6 單位長度的矩形紙如圖二，
圖二
其水平邊為 4 單位長度，垂直邊為 6 單位長度，畫上去的六條直線的端點分別為
Line 1: (0, 1), (4, 5)
Line 2: (0, 3), (4, 3)
Line 3: (0, 4), (4, 4)
Line 4: (0, 3), (3, 6)
Line 5: (0, 5), (4, 1)
Line 6: (1, 6), (4, 3)
其中分割出的三角形個數為 11。
輸入說明
第一行輸入三個非負整數 M、N 及 K 以空白區分，其中 M 及 N 分別代表矩形水平與垂直邊的長度，
K 則代表切割線的數目。其中1≤M≤50，1≤N≤50 ，且 0≤K≤296。
從第二行開始的 K 行，每一行輸入四個非負整數 X1、Y1、X2、及 Y2 以空白區分，
其中(X1, Y1)及(X2, Y2)分別代表一條切割線兩端點的水平及垂直座標位置(以矩型左下角為(0, 0))，
且兩端點一定落在該矩形的邊上。
K 則代表切割線的數目。其中1≤M≤50，1≤N≤50 ，且 0≤K≤296。
從第二行開始的 K 行，每一行輸入四個非負整數 X1、Y1、X2、及 Y2 以空白區分，
其中(X1, Y1)及(X2, Y2)分別代表一條切割線兩端點的水平及垂直座標位置(以矩型左下角為(0, 0))，
且兩端點一定落在該矩形的邊上。
輸出說明
顯示切割後產生的三角形個數。
範例輸入
#1
範例一 4 4 4 0 0 4 4 0 2 4 2 0 2 2 4 1 4 4 1 範例二 4 6 6 0 1 4 5 0 3 4 3 0 4 4 4 0 3 3 6 0 5 4 1 1 6 4 3
範例輸出
#1
範例一 4 範例二 11
測資資訊：
記憶體限制：
512
MB
公開 測資點#0 (11%): 1.0s , <1K
公開 測資點#1 (11%): 1.0s , <1M
公開 測資點#2 (11%): 1.0s , <1K
公開 測資點#3 (11%): 1.0s , <1K
公開 測資點#4 (11%): 1.0s , <1K
公開 測資點#5 (11%): 1.0s , <1M
公開 測資點#6 (11%): 1.0s , <1M
公開 測資點#7 (11%): 1.0s , <1K
公開 測資點#8 (12%): 1.0s , <1K
公開 測資點#0 (11%): 1.0s , <1K
公開 測資點#1 (11%): 1.0s , <1M
公開 測資點#2 (11%): 1.0s , <1K
公開 測資點#3 (11%): 1.0s , <1K
公開 測資點#4 (11%): 1.0s , <1K
公開 測資點#5 (11%): 1.0s , <1M
公開 測資點#6 (11%): 1.0s , <1M
公開 測資點#7 (11%): 1.0s , <1K
公開 測資點#8 (12%): 1.0s , <1K
提示 ：
因官方表示不公布測資，本題測資是自己生的
感謝建資100級ATP 幫忙測試
感謝建資100級ATP 幫忙測試
標籤:
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
|
沒有發現任何「解題報告」
|
|||||