题意：给点N棵树，前K棵是已经拥有的，现在可以再拥有一棵树，问形成的最大凸包面积。
思路：先求K棵树的凸包C，然后对于后面的N-K棵树，我们先判断是否在凸包内，如果不在，我们要求两个切线。 这里分类讨论，即可。
如果点在C的左边，那么两条切线分别一上一下； 如果在下边，两条切线一左一右。 然后去对应区间二分即可。
（好像还有双指针的线性做法：求两个凸包，维护两条切线即可。
#include<bits/stdc++.h> #define ll long long #define rep(i,a,b) for(int i=a;i<=b;i++) using namespace std; const int maxn=200010; struct point{ ll x,y; point(){} point(ll xx,ll yy):x(xx),y(yy){} }; bool cmp(point w,point v){ if(w.x!=v.x) return w.x<v.x; return w.y<v.y; } ll det(point a,point b){ return a.x*b.y-a.y*b.x;} ll dot(point a,point b){ return a.x*b.x+a.y*b.y;} point operator +(point a,point b){ return point(a.x+b.x,a.y+b.y);} point operator -(point a,point b){ return point(a.x-b.x,a.y-b.y);} point a[maxn],ch[maxn]; int top,ttop; void convexhull(int N) { for(int i=1;i<=N;i++){ while(top>1&&det(ch[top]-ch[top-1],a[i]-ch[top-1])<=0) top--; ch[++top]=a[i]; } ttop=top; for(int i=N-1;i>=1;i--){ while(top>ttop&&det(ch[top]-ch[top-1],a[i]-ch[top-1])<=0) top--; ch[++top]=a[i]; } } int get(int L,int R,int i,int w) { while(L<R){ int Mid=(L+R)>>1; if(det(ch[Mid]-a[i],ch[Mid+1]-a[i])*w>0) R=Mid; else L=Mid+1; } return L; } int bord(int L,int R,int i,int w) { while(L<R){ int Mid=(L+R)>>1; if((ch[Mid].x-a[i].x)*w<0) L=Mid+1; else R=Mid; } return L; } ll ans,sum[maxn],tmp; int main() { int N,K; scanf("%d%d",&N,&K); rep(i,1,N) scanf("%lld%lld",&a[i].x,&a[i].y); sort(a+1,a+K+1,cmp); convexhull(K); rep(i,1,top-1) ans+=det(ch[i],ch[i+1]),sum[i+1]=ans; rep(i,K+1,N){ if(a[i].x<ch[1].x){ int L=get(1,ttop,i,1),R=get(ttop,top,i,-1); tmp=sum[R]-sum[L]+det(ch[R],a[i])+det(a[i],ch[L]); } else if(a[i].x>ch[ttop].x){ int L=get(1,ttop,i,-1),R=get(ttop,top,i,1); tmp=sum[top]-sum[R]+sum[L]+det(ch[L],a[i])+det(a[i],ch[R]); } else if(det(ch[ttop]-a[1],a[i]-ch[1])>0){//shang int Mid=bord(ttop,top,i,-1); if(Mid>ttop&&det(ch[Mid]-ch[Mid-1],a[i]-ch[Mid-1])>0) continue; int L=Mid>ttop?get(ttop,Mid-1,i,-1):Mid; int R=get(Mid,top,i,1); tmp=sum[top]-sum[R]+sum[L]+det(ch[L],a[i])+det(a[i],ch[R]); } else { int Mid=bord(1,ttop,i,1); if(Mid>1&&det(ch[Mid]-ch[Mid-1],a[i]-ch[Mid-1])>0) continue; int L=Mid>1?get(1,Mid-1,i,-1):1; int R=get(Mid,ttop,i,1); tmp=sum[top]-sum[R]+sum[L]+det(ch[L],a[i])+det(a[i],ch[R]); } ans=max(ans,tmp); } printf("%lld.%lld ",ans/2,ans%2*5); return 0; } /* 5 3 -5 -5 -5 5 5 -5 -4 6 5 5 */