19号晚上九点十三分提的那个凸包问题 130C

请大神帮忙把代码补充完整,不要网站上已有的。。请将答案回复到两个提问下,总共一百五c币
#include
#include

// 通过结构体定义"点"类型
struct Point
{ double x, y; };

// 定义"向量"类型
// 实质上和上面的"点"是同一类型
// 在需要使用向量时,可以选择 Vector 这个名字
typedef Point Vector;

/////////////////////////////////////////////

// 输出一个点的坐标
void prtpoint( Point p )
{
printf("( %.2f, %.2f )\n", p.x, p.y );
}

// 判断给定的两个点是否是同一个点
// 是则返回true ,否则返回false
// 在比较两个点时,可以使用运算符 ==
bool operator==( Point p1, Point p2 )
{
if( fabs(p1.x-p2.x)<1e-9 && fabs(p1.y-p2.y)<1e-9 )
return true;
else
return false;
}

// 计算一个向量的模
double module( Vector v )
{
return sqrt( v.x*v.x + v.y*v.y );
}

// 计算两个向量夹角的余弦值
double cosab( Vector a, Vector b )
{
return ( a.x*b.x + a.y*b.y ) / module(a) / module(b);
}

/////////////////////////////////////////////////////////////////////////////////////
int main( )
{
// 陷井坐标,可以将其它测试数据直接放入数组中
Point trap[] = { { 0, 0 },{ 1, 1 },{ 3.1, 1.3 },{ 3, 4.5 },{ 6, 2.1 },{ 2, -3.2 } };

// 记录选作边界的点
Point perimeter[100]; 

// 陷井的个数和边界点的个数
int trapnum, perinum;

// 定义两个向量 va  vb;
Vector va, vb;

int i, k;
double maxcos;//最大余弦值

// 计算trap数组中元素的个数
trapnum = sizeof(trap) / sizeof(Point);
// 选作边界的点的个数,开始为0
perinum = 0;

// 通过比较横坐标,寻找最左边的一点
// k 记录其在trap中的下标
k = 0;  // 先假设trap[0]是最左边的点
        // 如果有更靠左的点,则修改k的值
///////////////////////////////////////////
// 此处需要补充代码,确定最左边的点




///////////////////////////////////////////

perimeter[0] = trap[k]; // trap[k]作为边界的第一个点,存放在perimeter[0]中
perinum++;              // 记数

// 向量va的初始值可以赋值为y轴的单位向量
va.x = 0;   va.y = 1;

// 寻找其它点
while( 1 )
{
    // 先给maxcos一个最小的值,当有更大值出现时,对其进行修改
    maxcos = -1;    // cos(90)

    // 在所有的点中寻找下一个点
    for(i = 0;i < trapnum;i++ )
    {
        // 计算前一个边界点 perimeter[perinum-1] 与 trap[i]构成的向量 vb

        ///////////////////////////////////////////
        // 此处需要补充代码




        ///////////////////////////////////////////
        // 计算两个向量va vb的夹角余弦,然后和maxcos比较
        // 如果比maxcos大,说明夹角更小,可以作为一个候选点
        // 用k记录这个点在trap中的下标
        ///////////////////////////////////////////
        // 此处需要补充代码




        ///////////////////////////////////////////

    }

    // trap[k]被选中,判断它是否是边界的第一个点
    // 如果是说明构成一个多边形,寻找过程结束
    if(  trap[k] == perimeter[0]  )
        break;

    // 如果是一个新出现的点,把它放入边界中
    perimeter[perinum] = trap[k];
    perinum++;
    // vb成为新的 va
    va.x = vb.x;
    va.y = vb.y;
}
// 

// 输出作为边界的点的坐标
for(i = 0; i < perinum;i++)
    prtpoint(perimeter[i]);
prtpoint(perimeter[0]);


return 0;

}

2个回答

需求不是很清楚?能不能贴一下之前的问题链接?

qq_37108068
qq_37108068 原题是一个布置陷阱抓飞蛾的问题,转化为数学问题就是平面中有的一系列点,连接其中的边界点组成一个凸多边形,使其他所有点在多边形中,具体步骤模板中都有说明,就是需要补充三处代码
3 年多之前 回复
qq_37108068
qq_37108068 我能力有限,这个网站里的程序真心看不懂,我只想把这个模板补充好。。。
3 年多之前 回复
Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问