【作业题,要求时间限制1000ms,内存限制2048KB,自己实在不会做,想请教大家怎么缩减内存,以及怎样判断凸多边形更简便】
问题描述
题目会给出二维空间中N个点的坐标,并且保证:按照题目给出顶点的顺序依次连接这些点,再将最后一个点与第一个点相连,可以构成一个N边形,并且这样连过的路径是顺时针方向的。请判断这个N边形是否为凸多边形。如果多边形非凸,还需要判断哪些顶点是凹点(凹点即该顶点处的内角大于180°)。
注意题目一次输入会给出K(K≥1)个多边形,需要分别对这K个多边形给出解答。
数据范围:0<K<100000, 2<N<1000.
输入格式
(共2K+1行)
第1行:正整数K,(代表有多少个多边形)
第2行:正整数Ni,(代表该多边形的边数)
第3行:2Ni个浮点数,以空格分离,代表顶点坐标(x0,y0), (x1,y1), …, (xNi-1,yNi-1)
...
...
输出格式
(共K行)
第i行对应第i个多边形的结果,
若为凸,则输出小写字符y;
若非凸,则按从小到大的顺序输出所有凹点的编号,这些编号来自输入顶点的顺序,编号从0开始。