假设使用者在绘图软体中,使用多边形绘图工具,依序使用滑鼠输入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。
2 5 2 0 0 0 4 1 3 3 1 1 3 10 21 32 45 18 79
7 3
編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」
|