b234. CSAPC'09 多邊形
標籤 :
通過比率 : 5人/15人 ( 33% ) [非即時]
評分方式:
Tolerant

最近更新 : 2012-01-02 00:27

內容

假设使用者在绘图软体中,使用多边形绘图工具,依序使用滑鼠输入P 1 、P 2 、…、P n共n个点的座标,则此绘图工具会自动产生n个相对应的线段(为方便起见,在本题中,我们假设这些线段皆不会与X轴或Y轴平行),分别是P 1 P 2 、P 2 P 3 、…、P n-1 P n 、P n P 1 。这n个线段彼此可能相交,也可能没有彼此相交。若我们将这些线段所围起来的所有区域涂上一样的颜色,我们将可以形成一个新的多边形。

例如,在下方的图例中,使用者共依次输入(1,0)、(3,2)、 (0,4)、(3,8)、(2,5)、(1,6)、( 4,7)七个点座标,且这些点座标相对应的线段彼此有相交的现象。若我们将所有线段所围起来的区域涂上一样的颜色后,我们可以得到一个新的11边形,其端点座标分别为(3,8)、(2.5,6.5)、(4,7) 、(2.1111,2.5926)、(3,2)、(1,0)、(2.1111,2.5926)、(0,4)、(1.2857,5.7143)、(1,6)、(1.6667,6.2222)。

 

 

注意,在这个新形成的多边形中,有些端点可能会重复出现。例如,在这个范例中,(2.1111,2.5926)因为刚好是两个线段的交会处,并且是两个子多边形的连接点,因此在新形成的多边形中,共出现了两次。

 

您的任务是根据依序输入的n个点座标,计算所形成的新的多边形共有几个端点。

 

輸入說明

输入的第一行为一个整数k,代表接下来有k组测试资料(k<=20)。每一组测试资料的第一行为一个整数n,代表此组测试资料中,共有n个输入点(3 <= n <= 100);接下来的n行中,第i行有两个以一个空白符号相间隔的整数,这两个整数依序代表第i个输入点的X与Y轴座标。为方便起见,我们假设所有的X与Y座标值皆大于等于0,且小于等于1000。

輸出說明
请针对每一组测试资料,输入图形化后的多边形端点座标数目。 (请依序在每一行输出一组测试资料的答案)
範例輸入 #1
2
5
2 0
0 0
4 1
3 3
1 1
3
10 21
32 45
18 79
範例輸出 #1
7
3
測資資訊:
記憶體限制: 512 MB
提示 :
占总分30%的测试数据中n<=6
占总分60%的测试数据中n<=20
占总分100%的测试数据中n<=100
//經查,這題的原測資中的第5測資檔第11行有誤,已更正並重測!——2012.1.2 00:30
標籤:
出處:
2009海峽兩岸青少年程式設計競賽陳伶志 [管理者: cclljj (cclljj) ]

本題狀況 本題討論 排行

編號 身分 題目 主題 人氣 發表日期
沒有發現任何「解題報告」