风送燕归来 雨幕开
停歇朝雨时 云叆叇
临窗迎春回 芳菲再
揽将春深处 青山入我怀
因为本人比较菜,所以今天只学习了一个算法:
Andrew算法
主体思路:
- 按照x优先的顺序排序(坐标从小到大)
- 从第一个点开始遍历,如果下一个点在栈顶的两个元素所连成直线的左边,那么就入栈;
- 否则如果在右边,说明凸包有更优的方案,上次的点出栈,并直到新点在栈顶两个点所在的直线的左边为止
- 翻译成人话就是贪心去找斜率最小的那个,这样显然回把所有的点都圈在里面
- 先从左到右跑一边求下凸包,之后从右往左再跑一边求上凸包,之后的细节在下面的代码会给出。
先来一个例题:
传送门
这个题可以把每个输入的数值,看成一个点(i,c[i])
之后不难发现,求得就是这个图的下凸包
上代码
#include <cstdio>
#include <iostream>
#include <algorithm>
#define N 1000005
#define LL long long
using namespace std;
int n,top;
struct NODE{
LL x,y;
}point[N],sta[N];
double ans=0.000;
inline int read(){
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){
x=x*10+ch-'0';ch=getchar();}
return x*f;
}
inline double lgr(NODE a,NODE b){
return(a.x*b.y-a.y*b.x);
}
inline double cal(NODE a,NODE b,NODE c){
NODE x1,x2;
x1.x=b.x-a.x;
x1.y=b.y-a.y;
x2.x=c.x-a.x;
x2.y=c.y-a.y;
return lgr(x1,x2);
}
int main(){
n=read();
for(int i=1;i<=n;i++){
scanf("%lld",&point[i].y);
point[i].x=i;
}
top=0;
sta[top].x=point[1].x;
sta[top].y=point[1].y;
top++;
sta[top].x=point[2].x;
sta[top].y=point[2].y;
for(int i=3;i<=n;i++){
while(top&&cal(sta[top-1],sta[top],point[i])<=0) top--;
top++;
sta[top].x=point[i].x;
sta[top].y=point[i].y;
}
for(int i=1;i<=top;i++){
ans+=(abs(sta[i].y+sta[i-1].y)*(sta[i].x-sta[i-1].x+1)/2.00000);
}
//cout<<top;
for(int i=1;i<top;i++){
ans-=sta[i].y;
}
printf("%.10lf",ans);
return 0;
}
真正的板子:
传送门
写板子的时候有两点注意:
- 在求上半凸包的时候,也要像求下半凸包一样,把第n-1个点先进栈,否则这个点可能会对下半凸包造成影响
- 上半凸包应循环到最后一个点,人话就是得连成一个闭环,有些碧落第一次没练成一个环,只得了2个点/kk
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#define N 1000005
#define LL long long
using namespace std;
int n,top;
struct NODE{
double x,y;
}point[N],sta[N];
inline int read(){
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){
x=x*10+ch-'0';ch=getchar();}
return x*f;
}
inline double lgr(NODE a,NODE b){
return(a.x*b.y-a.y*b.x);
}
inline double cal(NODE a,NODE b,NODE c){
NODE x1,x2;
x1.x=b.x-a.x;
x1.y=b.y-a.y;
x2.x=c.x-a.x;
x2.y=c.y-a.y;
return lgr(x1,x2);
}
inline bool cmp(NODE a,NODE b){
return a.x<b.x;
}
inline double cal2(NODE a,NODE b){
return sqrt(((a.x-b.x)*(a.x-b.x))+(a.y-b.y)*(a.y-b.y));
}
int main(){
n=read();
for(int i=1;i<=n;i++)scanf("%lf%lf",&point[i].x,&point[i].y);
sort(point+1,point+n+1,cmp);
top=0;
sta[top].x=point[1].x;
sta[top].y=point[1].y;
top++;
sta[top].x=point[2].x;
sta[top].y=point[2].y;
for(int i=3;i<=n;i++){
while(top&&cal(sta[top-1],sta[top],point[i])<=0) top--;
top++;
sta[top].x=point[i].x;
sta[top].y=point[i].y;
}
top++;
sta[top].x=point[n-1].x;
sta[top].y=point[n-1].y;
for(int i=n-2;i>=1;i--){
while(top&&cal(sta[top-1],sta[top],point[i])<=0) top--;
top++;
sta[top].x=point[i].x;
sta[top].y=point[i].y;
}
// cout<<sta[top].x<<sta[top].y<<" "<<endl;
double ans=0.0000;
for(int i=1;i<=top;i++)ans+=cal2(sta[i],sta[i-1]);
//ans+=cal2(sta[0],sta[top]);
printf("%.2lf",ans);
return 0;
}