今天开始计算几何之旅。
第一章讲的是凸包，之前接触过，想就草草开始下一章，但是想到要与队友共勉，还是认真的看了，来总结一下。
------------------------------------------------
凸包问题大致上就是求解一个点集的最外围点。图就不上了。了解凸包的模型，用模板一般就可以了。自己敲了个模板下文中会贴出来。A了hdu的两题凸包，验证了正确性。
暴力的做法O(n^3)。这里介绍一种O(n*log(n))的方法。
首先对点进行排序。x小的在前面，当x一样大小时，y小的在前面。这样我们就得到了最左边的点和最右边的点。
通过这两个点我们把凸包分成两部分。上半部分和下半部分。
你可以把凸包想象成一个圆，现在我们把圆分成了上下两个半圆。
现在我们有点集中的3个点。且3个点都是有序的如果点2在点1，3所成直线的下方。那么点2必然不属于上凸包。
如此。我们每次都判断从左到右的最后3个点是否符合要求如若不然删除中间的点既点2；这样一直到所有点都遍历了，我们就得到了上凸包；
同理可得下凸包
再介绍一下叉积，高等数学应该学过。他可以判断点在直线的上方还是下方。
如果纯文字看不明白，结合一下代码
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<cmath>
#include<iostream>
using namespace std;
const int MAX = 1e6+5;
const double pi = 3.1415926;
typedef int element;
struct Point{
element x , y ;
friend bool operator < ( Point p1 , Point p2 ){
return p1.x<p2.x || ( p1.x==p2.x && p1.y > p2.y );
}
};
double dist( Point p1 , Point p2 ){
return sqrt( (double)(p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y) );
}
struct Tubao{
Point lower[MAX] , upper[MAX];//分别保存上凸包和下凸包的点。
Point allPoint[MAX];
int Size;
int topLower , topUpper;
void init(){
sort(allPoint,allPoint+Size);
}
//叉积
element cross( Point p1, Point p2 , Point p3 ){
return (p2.x-p1.x)*(p3.y-p1.y)-(p2.y-p1.y)*(p3.x-p1.x);
}
void work(){
init();
topUpper = topLower = 0;
for(int i = 0 ; i < Size ; ++ i ){
while( cross( upper[topUpper-2] , upper[ topUpper-1 ] , allPoint[i] ) > 0 && topUpper >= 2 )
topUpper--;//删除不属于凸包上的点
upper[ topUpper++ ] = allPoint[i] ;
}
for(int i = Size-1 ; i >= 0 ; i-- ){
while( cross( lower[topLower-2] , lower[ topLower-1 ] , allPoint[i] ) > 0 && topLower >= 2 )
topLower --;
lower[ topLower++ ] = allPoint[i] ;
}
/*for( int i = 1 ; i < topUpper-1 ; ++ i )
lower[ topLower ++ ] = upper[ i ] ;*/
}
}Solve;
//以下非模板
int main(){
int t;scanf("%d",&t);
while(t--){
int m,k;
int n;scanf("%d%d%d",&k,&m,&n);
Solve.Size = n;
for(int i = 0 ; i < n ; ++ i )
scanf("%d%d" , &Solve.allPoint[i].x , &Solve.allPoint[i].y );
if(n==1){
puts("0.00");continue;
}
if(n==2){
printf("%.2lf\n" , dist(Solve.allPoint[0],Solve.allPoint[1]));continue;
}
Solve.work();
double ret = 0;
for(int i = 0 ; i < Solve.topLower ; ++ i ){
ret += max(0,-Solve.lower[i].x*k+Solve.lower[i].y*m);
}
for(int i = 1 ; i < Solve.topUpper-1 ; ++ i ){
ret += max(0,-Solve.upper[i].x*k+Solve.upper[i].y*m);
}
printf("%.0lf\n" , ret);
}
return 0;
}
/*
12 7
30 5
80 7
50 87
22 9
45 1
50 7
*/
与队友共勉：如果还是不理解凸包，我把电子书传到讨论组，可以看第一章。