gracegrapegrace 2017-10-09 11:44
浏览 1523

C++问题,关于凸多边形判定

【作业题,要求时间限制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开始。

  • 写回答

0条回答

    报告相同问题?

    悬赏问题

    • ¥20 iqoo11 如何下载安装工程模式
    • ¥15 本题的答案是不是有问题
    • ¥15 关于#r语言#的问题:(svydesign)为什么在一个大的数据集中抽取了一个小数据集
    • ¥15 C++使用Gunplot
    • ¥15 这个电路是如何实现路灯控制器的,原理是什么,怎么求解灯亮起后熄灭的时间如图?
    • ¥15 matlab数字图像处理频率域滤波
    • ¥15 在abaqus做了二维正交切削模型,给刀具添加了超声振动条件后输出切削力为什么比普通切削增大这么多
    • ¥15 ELGamal和paillier计算效率谁快?
    • ¥15 蓝桥杯单片机第十三届第一场,整点继电器吸合,5s后断开出现了问题
    • ¥15 file converter 转换格式失败 报错 Error marking filters as finished,如何解决?