}
//判断重心是否在范围内
point vec1, vec2;
vec1.x = mass.x - left.x; vec1.y = mass.y - left.y;
vec2.x = right.x - left.x; vec2.y = right.y - left.y;
if((vec1.x*vec2.x + vec1.y*vec2.y) < 0)
return -1;
vec1.x = mass.x - right.x; vec1.y = mass.y - right.y;
vec2.x = left.x - right.x; vec2.y = left.y - right.y;
if((vec1.x*vec2.x + vec1.y*vec2.y) < 0)
return -1;
return max_index;
}
//找到稳定的最小baseline
//mys:凸包中的点集;vertices:点集; mass:重心坐标
//返回最小的baseline
int find_stable(stack
{
vector
while(mys->size() > 0)
{
myv.push_back(mys->top());
mys->pop();
}
int min_index = 65535;
for(int i = 0; i < myv.size(); i++)
{
//确定直线公式
int this_min = cal_max(i,&myv,vertices,mass);
if(this_min >=0 && this_min < min_index)
{
min_index = this_min;
}
}
if(min_index == 65536)
return 0;
return min_index;
}
//判断向量方向是否向左
//index:将要判断的点的位置; mys:凸包中的点集; vertices:点集
//true: 满足要求; false:不满足，朝右
bool is_left(int index, stack
{
int first = mys->top();mys->pop();
int second = mys->top();mys->push(first);
point vec1,vec2;
point vec0;vec0.x = 0;
vec1.y = vertices->at(first).y - vertices->at(second).y;
vec1.x = vertices->at(first).x - vertices->at(second).x;
vec2.y = vertices->at(index).y;
vec2.x = vertices->at(index).x;
vec0.y = vertices->at(first).y - vertices->at(first).x*vec1.y/vec1.x;
if(vec1.x > 0)
{
if(vec2.y >= vec2.x*vec1.y/vec1.x + vec0.y)
return true;
}
else if(vec1.x < 0)
{
if(vec2.y <= vec2.x*vec1.y/vec1.x + vec0.y)
return true;
}
else
{
if(vec1.y * (vec2.x - vertices->at(first).x) <= 0)
return true;
}
return false;
}
//找到最小y坐标的点，放在0位置
//vertices:点集
void find_first(vector
{
for(int i = 0; i < vertices->size(); i++)
{
if(vertices->at(i).y < vertices->at(0).y)
swap(vertices->at(i), vertices->at(0));
}
}
//根据和0位置点的级角排序除第一个以外的所有点(偷懒用的插入排序...)
//vertices:点集
void sort(vector
{
for(int i = 1; i < vertices->size(); i++)
{
for(int j = i; j > 1; j--)
{
//使用向量余弦定理做，明天
point vec0,vec1,vec2;
vec0.x = 1;vec0.y = 0;
vec1.y = vertices->at(j).y - vertices->at(0).y;
vec1.x = vertices->at(j).x - vertices->at(0).x;
vec2.y = vertices->at(j-1).y - vertices->at(0).y;
vec2.x = vertices->at(j-1).x - vertices->at(0).x;
double cos1 = (vec1.x*vec0.x + vec1.y*vec0.y) / sqrt((vec1.x*vec1.x + vec1.y*vec1.y)*(vec0.x*vec0.x + vec0.y*vec0.y));
double cos2 = (vec2.x*vec0.x + vec2.y*vec0.y) / sqrt((vec2.x*vec2.x + vec2.y*vec2.y)*(vec0.x*vec0.x + vec0.y*vec0.y));
if(cos1 > cos2)
{
swap(vertices->at(j),vertices->at(j-1));
}
/*double rate1 = (vertices->at(j).y - vertices->at(0).y)/(vertices->at(j).x - vertices->at(0).x);
double rate2 = (vertices->at(j-1).y - vertices->at(0).y)/(vertices->at(j-1).x - vertices->at(0).x);
if(vertices->at(j).x - vertices->at(0).x == 0)
rate1 = 65535;
if(vertices->at(j-1).x - vertices->at(0).x == 0)
rate2 = 65535;