本节涉及计算几何,和 DP
Translate:USACO/fence4
Closed Fences 闭合的栅栏
译 by Jeru
描述
一个闭合的栅栏是平面上的一些不相交的首尾相连的线段形成的多边形，有
N 个角(顶点) (3 < N < 200)。 顶点不重合，它以逆时针方式以数组{x
i
, y
i
}给
出(i=1,2,...,N)。
每一对相邻的顶点都是一条栅栏。因此共有 N 条栅栏 (定义 x
N+1
=x1, y
N+1
=y1)。
这里有一个栅栏的例子和一个点 x,y:
* x3,y3
x5,y5 / \
x,y * * / \
/ \ / \
/ * \
x6,y6* x4,y4 \
| \
| \
x1,y1*----------------* x2,y2
请编写一个程序实现下面的任务:
检查输入的顶点列表{xi,yi}, i=1,2,...,N, 判断它是否为一个合法的闭合栅
栏。
评论0