MnZn求助!!
查看原帖
MnZn求助!!
239160
Jekyll_Y楼主2022/5/18 11:39

第二个点wa,救救孩子吧(/kk)

#include<bits/stdc++.h>
#define eps 1e-10
using namespace std;
const int maxn=2100;
struct geometric{
    double x,y;
    geometric(double X=0,double Y=0):x(X),y(Y) {}
    friend geometric operator + (const geometric a,const geometric b){return geometric(a.x+b.x,a.y+b.y);} 
    friend geometric operator - (const geometric a,const geometric b){return geometric(a.x-b.x,a.y-b.y);} 
    friend geometric operator * (const geometric a,double p){return geometric(a.x*p,a.y*p);}
    friend geometric operator / (const geometric a,double p){return geometric(a.x/p,a.y/p);}
}p[maxn],st[maxn];
double dis(geometric a,geometric b){return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));} 
double cross(geometric a1,geometric a2,geometric b1,geometric b2){return (a2.x-a1.x)*(b2.y-b1.y)-(a2.y-a1.y)*(b2.x-b1.x);} 
int n,cnt,top;double S=-1e20;
bool cmp(geometric a,geometric b)
{
    double tmp=cross(p[1],a,p[1],b);
    if(tmp>0)return true;
    if(tmp==0)return dis(p[1],a)<dis(p[1],b);
    return false;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        double x,y;
        scanf("%lf%lf",&x,&y);
        p[++cnt]=geometric(x,y);
        if(i==1)continue;
        if(p[cnt].y<p[1].y)swap(p[cnt],p[1]);
        if(p[cnt].y==p[1].y&&p[cnt].x>p[1].x)
            swap(p[cnt],p[1]);
    }
    sort(p+2,p+cnt+1,cmp);
    st[++top]=p[1];
    for(int i=2;i<=cnt;i++)
    {
        while(top>1&&cross(st[top-1],st[top],st[top],p[i])<eps)top--;
        st[++top]=p[i];
    }
    st[++top]=p[1];
    for(int i=2,j=3,l,r;i<=top;i++)
    {
        double s1,s2;
        while(cross(st[i-1],st[i],st[i-1],st[j])<=cross(st[i-1],st[i],st[i-1],st[j+1]))j++,j=(j==top+1?1:j);
        l=j+1,r=i+1;l=(l-1)%top,r=(r-1)%top;
        while(cross(st[i],st[j],st[i],st[l])-cross(st[i],st[j],st[i],st[l+1])<-eps)l++,l=(l==top+1?1:l);
        while(cross(st[j],st[i],st[j],st[r])-cross(st[j],st[i],st[j],st[r+1])<-eps)r++,r=(r==top+1?1:r);
        s1=fabs(cross(st[i],st[j],st[i],st[l]));
        s2=fabs(cross(st[j],st[i],st[j],st[r]));
        S=max(S,s1+s2);
    }
    printf("%.3lf",S/2.0);
    return 0;
}
2022/5/18 11:39
加载中...