【文件属性】：
文件名称：凸包面积的计算~~~~
文件大小：2KB
文件格式：CPP
更新时间：2013-06-07 13:21:42
凸包
stack s;
cin>>n;
for(i = 0; i < n; i++)
cin>>pot[i].x>>pot[i].y;
x = pot[0].x;
y = pot[0].y;
p = 0;
for(i = 1; i < n; i++) //寻找最左上的点
{
if(pot[i].y < y || (pot[i].y == y && pot[i].x < x))
{
x = pot[i].x;
y = pot[i].y;
p = i;
}
}
p0.x = x;
p0.y = y;
swap(pot[0], pot[p]);
sort(pot + 1, pot + n, cmp); //排序
s.push(p0);
s.push(pot[1]);
s.push(pot[2]);
point t;
for(i = 3; i < n; i++) //凸包
{
while(!s.empty())
{
t = s.top();
s.pop();
p = ( pot[i].x-s.top().x)*(t.y-s.top().y) - (t.x-s.top().x)*(pot[i].y-s.top().y );
if(p < 0)
{
s.push(t);
break;
}
}
s.push(pot[i]);
}
double area = 0;
t = s.top();
s.pop();
area += (p0.x * t.y - p0.y * t.x)/2.0;
while(!s.empty())
{
area += (t.x * s.top().y - t.y * s.top().x)/2.0;
t = s.top();
s.pop();
}
if(area < 0)
area = -area;
cout<
