用C语言实现多边形顶点计算的一个问题,具体看下面

Problem Description
Given a set of distinct points S on a plane, we define a convex hole to be a convex polygon having any of thegiven points as vertices and not containing any of the given points in its interior. In addition to the vertices, other given points may lie on the perimeter of the polygon. We want to find a convex hole as above forming the convexpolygon with the largest area.

Input
This problem has several test cases.
The first line of input contains an integer t (1 ≤ t ≤ 100) indicating the total number of cases. For each test case,the first line contains the integer n (3 ≤ n ≤ 50). Each of the following n lines describes a point with two integers x and y where -1000 ≤ x, y ≤ 1000.
We guarantee that there exists at least one non-degenerated convex polygon.

Output
For each test case, output the largest area of empty convex polygon, with the precision of 1 digit.
Remark: The corollary of Pick’s theorem about the polygon with integer coordinates in that says the area of it iseither ends to .0 or .5.

Sample Input
4
3
0 0
1 0
0 1
5
0 0
1 0
2 0
0 1
1 1
5
0 0
3 0
4 1
3 5
-1 3
6
3 1
1 0
2 0
3 0
4 0
5 0

Sample Output
0.5
1.5
17.0
2.0

1个回答

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

相似问题

1
小白求助,Python怎么提取二值图中的矩形和多边形顶点坐标呢?
1
arcgis engine 绘制多边形outline设置width属性时是否可以让宽度不要超过多边形边缘(向内增宽)?
0
计算多边形有多少个面的问题,怎么利用C程序的代码的编写来实现呢
4
C 语言 检测点是否在凸边行内侧,学校算法作业一部分 检测是否是凸边行
0
运用数据结构建立多边形的联通的算法,怎么采用C程序的代码的编写的步骤才能实现?
1
请问怎么用VS来绘制三次B样条曲线?
0
多边形的切割的问题,怎么使用C语言的程序编写代码的形式方法去解决呢,具体代码编写
0
多边形的顶点的构建问题,是如何采用C语言的程序设计的思想方法加以有效实现的呢
0
面积大者在前面输出。(输出部分要四舍五入到整数),这个问题具体用C语言的实现做法
0
百度地图构建多边形交叉问题。
0
输出二维平面凸多边形的问题,使用C程序的代码设计的方式和步骤来计算的实现的思路
2
dxf如何画出只有轮廓的图形(包括多边形)
4
UE4 如何在UMG上绘制多边形并填充颜色?
1
MFC 多边形移动后留下虚线边框
0
C程序的语言,Shape of HDU
0
openLayers想在插入的图片上进行矩形或者多边形标注得到自己标注的矩形与图片之间的像素距离是多少?
3
GDI+绘图问题,内存位图是否支持透明通道
2
Python turtle为什么不绘制
2
求助一道C语言数结构体题目
0
Area 具体怎么实现