凸包+三分哪崩了???
查看原帖
凸包+三分哪崩了???
48146
ezoiHY楼主2018/12/19 18:24
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
  
using namespace std;
  
int n,top,tmp=1;
double ans;
  
struct node{
    double x,y,att;
    bool operator < (const node &b) const {
        return att==b.att?x<b.x:att<b.att; 
    }
}s[100001],p[100001];
  
double cp(node a1,node a2,node b1,node b2){
    return (a2.x-a1.x)*(b2.y-b1.y)-(a2.y-a1.y)*(b2.x-b1.x);
}
  
double dis(node p1,node p2){        
    return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));
}
  
double dis2(double A,double B,double C,double x0,double y0){
    return abs((A*x0+B*y0+C)/sqrt(A*A+B*B));
}
  
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%lf%lf",&p[i].x,&p[i].y);
        if(p[i].y<p[tmp].y or (p[i].y==p[tmp].y and p[i].x<p[tmp].x)){
            tmp=i;
        }
    }
    swap(p[1],p[tmp]);
    for(int i=2;i<=n;i++){
        p[i].att=atan2(p[i].x-p[1].x,p[i].y-p[1].y);
    }
    sort(p+2,p+n+1);
    s[++top]=p[1];
    for(int i=2;i<=n;i++){
        while(top>1 and cp(s[top-1],s[top],s[top],p[i])>=0){
            top--;
        }
        s[++top]=p[i];
    }
    for(int i=1;i<=top;i++){
        for(int j=i+2;abs(i-j)>=2;j++,j%=top){
        	j%=top;
            if(j==0)j=top;
            double k=(s[i].y-s[j].y)/(s[i].x-s[j].x),b=s[i].y-k*s[i].x;
            double d=dis(s[i],s[j]);
            double cmps=0;
            int l,r;
            if(i<j){
                l=i+1,r=j-1;
                while(l<r){
                    int midl=(l*2+r)/3,midr=(l+r*2)/3;
                    double tmpl=dis2(k,-1,b,s[midl].x,s[midl].y);
                    double tmpr=dis2(k,-1,b,s[midr].x,s[midr].y);
                    if(tmpl>tmpr){
                        r=midr;
                    }else {
                        l=midl;
                    }
                }
                cmps+=d*dis2(k,-1,b,s[l].x,s[l].y);
                l=i-1,r=(j+1)%top;
                if(r==0)r=top;
                l-=r;
                int aa=r;
                r=top;
                l=(l+top)%top;
                if(l==0)l=top;
                while(l<r){
                    int midl=(l*2+r)/3,midr=(l+r*2)/3;
                    double tmpl=dis2(k,-1,b,s[(midl+aa)%top!=0?(midl+aa)%top:top].x,s[(midl+aa)%top!=0?(midl+aa)%top:top].y);
                    double tmpr=dis2(k,-1,b,s[(midr+aa)%top!=0?(midr+aa)%top:top].x,s[(midr+aa)%top!=0?(midr+aa)%top:top].y);
                    if(tmpl>tmpr){
                        r=midr;
                    }else {
                        l=midl;
                    }
                }
                cmps+=d*dis2(k,-1,b,s[(r+aa)%top!=0?(r+aa)%top:top].x,s[(r+aa)%top!=0?(r+aa)%top:top].y);
            }else {
				l=i-1,r=j+1;
                while(l<r){
                    int midl=(l*2+r)/3,midr=(l+r*2)/3;
                    double tmpl=dis2(k,-1,b,s[midl].x,s[midl].y);
                    double tmpr=dis2(k,-1,b,s[midr].x,s[midr].y);
                    if(tmpl>tmpr){
                        r=midr;
                    }else {
                        l=midl;
                    }
                }
                cmps+=d*dis2(k,-1,b,s[l].x,s[l].y);
                l=(i+1)%top,r=j-1;
                if(l==0)l=top;
                l-=r;
                int aa=r;
                r=top;
                l=(l+top)%top;
                if(l==0)l=top;
                while(l<r){
                    int midl=(l*2+r)/3,midr=(l+r*2)/3;
                    double tmpl=dis2(k,-1,b,s[(midl+aa)%top!=0?(midl+aa)%top:top].x,s[(midl+aa)%top!=0?(midl+aa)%top:top].y);
                    double tmpr=dis2(k,-1,b,s[(midr+aa)%top!=0?(midr+aa)%top:top].x,s[(midr+aa)%top!=0?(midr+aa)%top:top].y);
                    if(tmpl>tmpr){
                        r=midr;
                    }else {
                        l=midl;
                    }
                }
                cmps+=d*dis2(k,-1,b,s[(r+aa)%top!=0?(r+aa)%top:top].x,s[(r+aa)%top!=0?(r+aa)%top:top].y);
            }
            ans=max(ans,cmps);
        }
    }
    printf("%.3lf",ans/2);
    return 0;
}
2018/12/19 18:24
加载中...