Description
给你N个点,请循环完成下列任务 1:求出这N个点的凸包的面积 2:拿掉最左或最右或最上或最下的一个点,当点的个数不足三个时停止
Input
第一行,一个数字N 接下来N行,每行两个数Xi,Yi 接下来,一个字符串,表示每次拿走的点(仅为UDLR代表上下左右)
Output
输出有N-2行,每行一个实数,保留一位小数
预处理删点顺序，逆序加点，用set和链表维护凸包上的点的极角序（以最初凸包内一点为原点），每次更新凸包时计算面积的变化量。
#include<bits/stdc++.h>
typedef long long i64;
int _(){
int x=,c=getchar();
while(c<)c=getchar();
while(c>)x=x*+c-,c=getchar();
return x;
}
int n;
double xs=,ys=;
struct _pos{
int id;
double a;
bool operator<(const _pos&w)const{return a<w.a;}
};
std::set<_pos>ss;
struct pos{
int x,y,id;
_pos get(){return(_pos){id,std::atan2(y-ys,x-xs)};}
}ps[],ps2[],ps0[];
bool cx(const pos&a,const pos&b){return a.x<b.x;}
bool cy(const pos&a,const pos&b){return a.y<b.y;}
char s[];
bool del[];
int ds[],dp=,nx[],pv[],cs[],ap=;
i64 ans=,as[];
bool chk(int a,int b,int c){
return i64(ps0[a].x-ps0[b].x)*(ps0[c].y-ps0[b].y)-i64(ps0[c].x-ps0[b].x)*(ps0[a].y-ps0[b].y)>=;
}
void cal(int a,int b,int c){
ans+=i64(ps0[c].x-ps0[b].x)*(ps0[a].y-ps0[b].y)-i64(ps0[a].x-ps0[b].x)*(ps0[c].y-ps0[b].y);
}
void dels(int w){
cal(nx[w],w,pv[w]);
nx[pv[w]]=nx[w];
pv[nx[w]]=pv[w];
ss.erase(ss.find(ps0[w].get()));
}
void inss(int l,int a,int r,_pos w){
cal(l,a,r);
nx[pv[a]=l]=pv[nx[a]=r]=a;
ss.insert(w);
}
int main(){
n=_();
for(int i=;i<n;++i){
ps[i].x=_();
ps[i].y=_();
ps[i].id=i;
}
memcpy(ps2,ps,sizeof(pos)*n);
memcpy(ps0,ps,sizeof(pos)*n);
std::sort(ps,ps+n,cx);
std::sort(ps2,ps2+n,cy);
int l1=,r1=n-,l2=,r2=n-;
scanf("%s",s);
for(int i=;s[i];++i){
if(s[i]=='L'){
while(del[ps[l1].id])++l1;
del[ds[dp++]=ps[l1++].id]=;
}else
if(s[i]=='R'){
while(del[ps[r1].id])--r1;
del[ds[dp++]=ps[r1--].id]=;
}else
if(s[i]=='D'){
while(del[ps2[l2].id])++l2;
del[ds[dp++]=ps2[l2++].id]=;
}else{
while(del[ps2[r2].id])--r2;
del[ds[dp++]=ps2[r2--].id]=;
}
}
int cp=;
for(int i=l1;i<=r1;++i)if(!del[ps[i].id]){
xs+=ps[i].x;
ys+=ps[i].y;
cs[cp++]=ps[i].id;
}
xs/=;ys/=;
ss.insert(ps0[cs[]].get());
ss.insert(ps0[cs[]].get());
pv[cs[]]=nx[cs[]]=cs[];
pv[cs[]]=nx[cs[]]=cs[];
while(dp){
int a=ds[--dp];
_pos w=ps0[a].get();
std::set<_pos>::iterator it=ss.lower_bound(w);
if(it==ss.end())it=ss.begin();
int r=it->id,l=pv[r];
if(!chk(l,a,r)){
while(chk(a,r,nx[r]))dels(r),r=nx[r];
while(chk(pv[l],l,a))dels(l),l=pv[l];
inss(l,a,r,w);
}
as[ap++]=ans;
}
while(ap){
ans=as[--ap];
printf("%lld.%lld\n",ans>>,*(ans&));
}
return ;
}