a074. TOI2011 第五題:畫作問題
Tags :
Accepted rate : 35人/48人 ( 73% ) [非即時]
評分方式:
Tolerant

最近更新 : 2014-11-01 02:08

Content
有一個現代藝術創作者,他的作品主要是以線條將空間分割成一些幾何圖形區域,再對各幾何圖形區域進行著色。
他特別創造了一系列的作品--直線與 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。
Input
第一行輸入三個非負整數 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)),
且兩端點一定落在該矩形的邊上。
Output
顯示切割後產生的三角形個數。
Sample Input #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 
Sample Output #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
Hint :
因官方表示不公布測資,本題測資是自己生的
感謝建資100級ATP 幫忙測試
Tags:
出處:
2011TOI研習營初選 [管理者: david942j (文旋) ]

Status Forum 排行

ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」