凸包面积的计算~~~~

【文件属性】：
文件名称：凸包面积的计算~~~~
文件大小：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<