題目中所描述：
「list of points might be clockwise or couter-clockwise」
的意思應該是說input file列出的連續兩點應該是形成一個邊?
如果是這樣的話每一點都應該是polygon的一個90度角的頂點，
也就是說點的x(or y)座標在檔案中是剛好出現連續兩次一樣的。
但在測試檔的case1的第一個75邊形卻發現不是這樣 :
0 16000
0 20000
0 25000
0 30000
以上列的前四點來說，如果連續兩點形成一個邊，
則上述四點只會形成一個直線，第二和第三點會變成沒有用，
那input file中第二第三點不是可以忽略不用列嗎？
那實際處理不就不用理第二點和第三點了？
*A1:
The meaning of "list of points might be clockwise or counter-clockwise"
is in a GLOBAL sense, not a LOCAL sense. It does not mean that
each point could be clockwise or counter-clokwise LOCALLY. It means that
the point list of the WHOLE polygon could be closkwise or
counter-closkwise. If you reverse the order of points of any feasible
input polygon, it is still a feasible input and in fact it represents the
same polygon. Hence there is no problem for several consective points on
the same line.
For the last issue about the 2nd and 3rd points mentioned in the question,
the answer is YES. You can neglect these kind of points. You could
remove these kind of points in preprocessing.
*Q2:
input的好幾個polygon可能
會grow長大後併成一個polygon嗎?
因為題目中並沒有說明這種情況的發生...
*A2:
Please consider each input polygon SEPARATELY. The reason to combine many
input polygon into a file is for evaluation. I want evaluate the
correctness and performance of your program by using few input files.
*Q2_2:
「input的好幾個polygon可能會grow長大後併成一個polygon嗎?
因為題目中並沒有說明這種情況的發生...」
但我不太懂出題者回答的後兩行的意思：
「The reason to combine many input polygon into a file is
for evaluation. I want evaluate the correctness and
performance of your program by using few input files.」
是不是就是不用考慮同一個 input file 中的polygons之間會長大
合併的問題 ?
換句話說，下列這種 input file 是否不會存在 ?
1
4
1 1
2 1
2 2
1 2
1
4
3 1
4 1
4 2
3 2
上述這兩個邊長為1的小正方形長大後應會合併成一個長方形
*A2_2:
Each input polygon is independently as a problem for its own. Each
output polygon list is also independently as a result for the input
polygon. If there are 10 input polygons in a input file, the output file
should have 10 polygon lists. Hence, it is not considered for combining
overlapped input or output polygons. The reason is I don't want to
evaluate your program by using 1000 files, where each file contains one
input polygon. But I would like to use one file containing 1000 input
polygons to evaluate the correctness and performance.
The test case mentioned is a possible one. You should not combine the
two output into one larger polygon.
*Q3: (4/9, 2002)
想請問一下兩個問題：
(1) 在最後評審在評估程式時，是實際CPU time比較重要還是
Time complexity比較重要？
(2) 最後保留的3-5個測試檔的 polygon size 最大到多大？
謝謝！
*A3:
The Reply from avanti is as belows:
Yes, both run time and memory usage will be evaluated. I think
run time seems to be more important to me in the evaluation. One reason
is that it is easier and more accurate to evaluate run time. The other is
using too much memory will also affect run time or even worst kill the
run.
I have not prepare the final evaluation testcases yet. I think the data
size will be at least several thousands polygons and several thousand
points in the largest polygon.
*Q4: (5/5, 2002)
想請問一下兩個問題：
(1) 題目中的多邊形的轉角都是直角的嗎 ? 因為在原始題目中解說有一個三角形的圖形,而且現今也有 45 度角的 layout ,但是目前提供的測試檔都是直角的多邊形,不知是否要考慮非直角的情形 ?(2) 下面這個圖形 輸入檔要如何表示也就是一個多邊形中有一個洞,由於這種情形需要兩個多邊形才能表示,但在之前的問答中出題者似乎是在輸入檔中是要以一個順/逆時針的點陣列來表示,但這種情形就無法表示了.......
A4:
On page 3 of 1.pdf, "only
rectilinear simple polygons are considered as
input
shapes." That's why the testcases all contain rectilinear
polygons
only.The example in page 3 is for explanation
purpose. Non-orthgonal
shapes will result in rounding errors and
it is much more challenging. It
will be too hard for you to write
robust code and too hard for me to
evaluating the correctness of your
program.
The output polygon may not be "simple". You have to
output this polygon
as a polygon list defined in page 4. Please
refer to the last example in
1.pdf. It is just the polygon with a
hole. You will figure out how to
represent this kind of
polygons.