其實求解思路倒也不復雜，就是先找到所有頂點的凸包(convex hull)，然後找到這些凸包點中每條相鄰點連成的直線，同時找到直線在多邊形中的端點，如Object1中1,2,5,6這條直線，端點就是1,6。如果重心和這兩個點的連線和直線都是銳角的話，那麼這條直線就是穩定的，就可以找到題目要求的所謂最小點了。我的代碼自己測試是沒問題的，但怎麼都Presentation Error，無語。找凸包用的是Graham's Scan方法。
[cpp]
#include <iostream>
#include <stack>
#include <vector>
#include <math.h>
#include <iomanip>
using namespace std;
typedef struct point
{
double x;
double y;
int index;//記錄點的index
}point;
int cal_max(int index, vector<int>* myv, vector<point>* vertices, point mass);
int find_stable(stack<int>* mys, vector<point>* vertices, point mass);
void find_first(vector<point>* vertices);
void sort(vector<point>* vertices);
bool is_left(int index, stack<int>* mys, vector<point>* vertices);
void find_convex_hull(vector<point>* vertices, stack<int>* mys);
int main()
{
char name[20];
vector<point> vertices;
stack<int> mys;
point mass;
while(cin>>name)
{
vertices.clear();
while(mys.size() > 0)
mys.pop();
if(strcmp(name,"#") == 0)
{
return 0;
}
cin>>mass.x>>mass.y;
point tmp;int index = 0;
while(cin>>tmp.x>>tmp.y)
{
if(tmp.x == 0 && tmp.y == 0)
{
break;
}
tmp.index = ++index;
vertices.push_back(tmp);
}
find_convex_hull(&vertices, &mys);//尋找凸包
int min = find_stable(&mys,&vertices,mass);
cout<<setw(20)<<setiosflags(ios::left)<<name<<setw(1)<<min<<endl;
//cout << name << ' ' << min << endl;
}
}
//尋找凸包的Graham's Scan法
//vertices:點集， mys:凸包的stack
void find_convex_hull(vector<point>* vertices, stack<int>* mys)
{
find_first(vertices);//找到y坐標最小的點，放在第一位
sort(vertices);//根據和y0角度坐標排序
mys->push(0);mys->push(1);mys->push(2);
for(int i = 3; i < vertices->size(); i++)
{
int pos = mys->top();
while(!is_left(i,mys,vertices))
{
mys->pop();
}
mys->push(i);
}
}
//計算myv中index和index+1組成的直線的最大baseline
//myv:凸包中的點集; vertices:點集; mass:重心坐標
//返回最大的baseline
int cal_max(int index, vector<int>* myv, vector<point>* vertices, point mass)
{
int start = index, end = index+1;
if(end == myv->size())
end = 0;
start = myv->at(start);end = myv->at(end);
point left, right;
int max_index = 0, min_x = 65535, max_x = -65535;
for(int i = 0; i < myv->size(); i++)
{
int ano = myv->at(i);
double rate1 = (vertices->at(end).y - vertices->at(start).y)/(vertices->at(end).x - vertices->at(start).x);
double rate2 = (vertices->at(ano).y - vertices->at(start).y)/(vertices->at(ano).x - vertices->at(start).x);
if(vertices->at(ano).x == vertices->at(start).x)
rate2 = (vertices->at(ano).y - vertices->at(end).y)/(vertices->at(ano).x - vertices->at(end).x);
if(vertices->at(ano).x == vertices->at(start).x && vertices->at(end).x == vertices->at(start).x)
rate2 = rate1 = 1;
if(rate1 == rate2)
{
if(vertices->at(ano).index > max_index)
max_index = vertices->at(ano).index;
if(vertices->at(ano).x > max_x)
{
max_x = vertices->at(ano).x;
right = vertices->at(ano);
}
if(vertices->at(ano).x < min_x)
{
min_x = vertices->at(ano).x;
left = vertices->at(ano);
}
}
}
//判斷重心是否在范圍內
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<int>* mys, vector<point>* vertices, point mass)
{
vector<int> myv;
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>* mys, vector<point>* vertices)
{
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<point>* vertices)
{
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<point>* vertices)
{
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;
if(rate1*rate2 > 0 && rate1 < rate2)
{
swap(vertices->at(j),vertices->at(j-1));
}
else if(rate1*rate2 < 0 && rate1 < 0)
{
swap(vertices->at(j),vertices->at(j-1));
}
else if(rate1*rate2 == 0 && (vertices->at(j).x > vertices->at(0).x || vertices->at(j-1).x < vertices->at(0).x))
{
swap(vertices->at(j),vertices->at(j-1));
}*/
}
}
}
