C++/凸多边形判定/简单算法/急 50C

【作业题,要求时间限制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开始。
输入示例
2
3
0 0 0.5 1 1 0
5
0 0 0.25 1 0.5 0.5 0.75 1 1 0
输出示例
y
2

1个回答

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问