*Q1: 我想問一個問題,就是你給我們的圖形繪不繪有所謂 “ 回“ 字型的圖形 如果有的話,那如何給一開始的座標呢?? *A1: If we are talking about a single polygon from the input file, the answer is NO. An O-shape polygon is treated as an invalid input and should be detected by the program. But notice that, two overlapped polygons can form an O-shape polygon correctly. ========================================================================== *Q2: 1. testcase 中，所給定的Polygon座標點，有沒有順時針或是逆時針的順序 ? 因為如果不給定順序的話，同一些點所構成的多邊形並不是唯一的。 2. 輸出檔中所要求的記憶体使用量，是實際所使用的記憶体量嗎 ? 請問是 否有什麼方式，可以在程式中求得程式的記憶体使用量 ? *A2: Answer for Question 1: Both clockwise and counterclockwise are acceptable. I don't understand what is the meaning of "not unique" in the question. Answer for Question 2: You might need to do some bookkeeping job when melloc() something. ========================================================================== *Q3: 請問程式可以寫兩種版本嗎? 因為只處理Vertical and Horizontal edge會比處理包含non-Vertical and non-Horizontal edge還快很多,若只能有一種版本,執行時間一定遜於只處理Vertical and Horizontal edge的版本.請告知,謝謝 *A3: I suggest you to submit the faster version of code. You could mention in your presentation that your algorithm is also ok to apply to non-vertical and non-horizontal edges. ========================================================================== *Q4: 請問題目規定要OUTPUT記憶體使用量 但是C語言好像沒有提供此功能 要得知確實的記憶體使用量好像要靠作業系統 因為程式中有很多區域變數, 我們無法得知確實的記憶體用量.是否能以書面報告的方式(系統追蹤) 而不從程式REPORT,如此比較合理,還是能提供我們相關資訊,謝謝. *A4: It is ok. Correctness and speed are the major concerns. ========================================================================== *Q5: 題目中寫要找出下面的錯誤 the self-intersection of edges in a 如果現在有CELL A和B不相交 但是B裡的polygon有self-intersection錯誤 如果執行a.out case1.dat A 此時我們要檢查出CELL B是錯誤的嗎?? *A5: I think the answer is NO. But it is still ok if you check that too. This behavior is out of the concern of this problem. Both are considered ok. ========================================================================== *Q6: 請問一下一個CELL中的REFERENCE會不會互相cover? 例如A cell包含reference (a) (b),(a)和(b)各有自己的polygan, (a)的polygan會不會和(b)的polygan有重疊. *A6: Yes, it is possible. ========================================================================== *Q7: The "Input Format" in Bachus Naur Form defines that: ::= 'BGNCEL' * 'ENDCEL' But, the input format of in the test cases is as follows: ... BGNCELL A ... ENDCELL ... The question I want to ask is that which one is correct (single L or double L or both of them). Please give me the answer, thank you ! :) *A7: I am sorry that I did not notice this mistake. I prefer to use the BNF definition. But, anyone of BGNCEL and BGNCELL will be ok for testing. This means that I will test your program with two possibilities. Anyone ok is ok. ========================================================================== *Q8: (please refer to http://www.cs.nthu.edu.tw/~cad/Problems/P6/1.jpg to find the figure) 同一層不同的reference是有可能會重疊的囉 即發生下面的情形嗎 *A8: Yes. Please do consider this case. ========================================================================== *Q9: 請問一下，在此題題目的 BNF of input format 中： ::= 是指 Cell or Reference Cell 的名稱可由任何字元組成嗎？ 還是說是由[A-Za-z]所開頭的字串呢？ *A9: Yes! Any printable character is ok. New-line, tab and space characters might be used as separators of tokens. ========================================================================== *Q10: 請問一下，我們是否需要偵測 cell name 重複定義的情況呢？ ex : BGNCELL A BGNPOLY 10 20 10 10 -20 10 ENDPOLY ENDCELL . . . BGNCELL A BGNPOLY 30 20 30 -10 70 -10 70 20 ENDPOLY ENDCELL *A10: It is good that your program can detect duplicate cell definitions. But I am not plan to use this kind of testcases to evaluate your program. ========================================================================== *Q11: 1. ::= 請問此處的Cell Name有無上限,或是我們可以自己規定其長度,然後在報告中說明? 2.::='BGNPOLY' * 'ENDPOLY' 請問當Polygon為一個點或一直線時,請問其面積為0,還是我們要輸出Error Message? *A11: For 1, let's limit the length to 128 characters. No testcases for evaluating your program will have names longer than 128 characters. For 2, please just treat the area as 0. ========================================================================== *Q12: 請問這樣算是self-intersection 嗎 BNGPOLY 0 0 1 0 1 1 0 1 0 2 -1 2 -1 1 0 1 ENDPOLY 即下面這種情形 +----+ | | | | +----+----+ | | | | +----+ *A12: Please treat this as a valid input. ========================================================================== *Q13: 在題目中 有可能出現 Cell A ref Cell B Cell B ref Cell C Cell C ref Cell A 此類題型嗎 ?? *A13: No, it is not allowed and will not be in the testcases. ========================================================================== *Q14: 我想請問一個問題,在題目中有提到: could be any 32-bit signed integer. 請問若我們的程式能夠處理浮點數,那我們可以使用 浮點數當做嗎? *A14: The input uses integers. You can use doubles in your internal data-structures as long as the results are correct. ========================================================================== *Q15: 請問一下，若 input file 有 syntax error，但是不影響計算 使用者指定的 cell area 時，我們需要偵測出嗎？ ex : 假設指定求 the area of cell A，那我們在讀完第七行後， 便可求得。但，如果要偵測最後一行的 syntax error 時， 便得多做許多次 file I/O，這會使得執行速度變慢。 BGNLIB BGNCELL A BGNPOLY 10 20 10 10 -20 10 ENDPOLY ENDCELL . . . NEDLIB (should be "ENDLIB") *A15: I prefer to report the error. But this is really not a important concern in the contest. I can't see why the performance will be affected. Anyway, there will be no this kind of testcases to be used. BOTH WAYS ARE OK! No testcases will show this differences. ========================================================================== *Q16: 請問一下能說明self-intersection的定義嗎?? *A16: There are "area (>0) overlapped". ========================================================================== *Q17: 你說There are "area (>0) overlapped".就是self-intersection 那(0,0)(0,1)(2,1)(2,2)(1,2)(1,0)就沒有self-intersection嗎?? 是否可以舉一個self-intersection的例子呢? *A17: Ya! That definition is not clear. Here is a new definition: NOTE THE FOLLOWING CHANGE: Let's make it simple. If you draw the edges, for each edge, only its two ends are allowed to touch other edges. Otherwise, self-intersection exists. This indicates the case of (0,0)(1,0)(1,1)(2,1)(2,2)(1,2)(1,1)(0,1) is valid. (0,0)(1,0)(1,2)(2,2)(2,1)(0,1), however, is NOT valid. ==========================================================================