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

Question

【作业题，要求时间限制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

Answer 1

http://www.leleketang.com/lib/40801804.shtml