样例过了但是全部wa是为什么?没道理的事
查看原帖
样例过了但是全部wa是为什么?没道理的事
606022
atomicbomb楼主2022/7/9 03:36
#include<bits/stdc++.h>
using namespace std;
const double eps=1e-8;
const double inf=1e20;
int sgn(double x)
{
    if(fabs(x)<eps) return 0;
    else return x<0?-1:1;
}
struct point
{
    double x,y;
    point(double X=0,double Y=0):x(X),y(Y){}
    point operator+(point b){return point(x+b.x,y+b.y);}
    point operator-(point b){return point(x-b.x,y-b.y);}
    point operator*(double k){return point(x*k,y*k);}
    point operator/(double k){return point(x/k,y/k);}
    bool operator==(point b)
    {
        return sgn(x-b.x)==0&&sgn(y-b.y)==0;
    }
    bool operator<(point b)
    {
        return sgn(x-b.x)<0||(sgn(x-b.x)==0&&sgn(y-b.y)<0);
    }
};
typedef point vec;
double cross(vec a,vec b){return a.x*b.y-a.y*b.x;}
double dot(vec a,vec b){return a.x*b.x+a.y*b.y;}
double dis(point a,point b){return hypot(a.x-b.x,a.y-b.y);}
double len(vec a){return sqrt(dot(a,a));}
double len2(vec a){return dot(a,a);}
vec rotate_vec(vec a)//旋转九十度
{
    return vec(-a.y,a.x);
}
point touyin(point p,point a,point b)
{
    double k=dot(b-a,p-a)/len2(b-a);
    return a+(b-a)*k;
}
double diantoxian(point a,point b,point c)//ab是直线端点
{
    return fabs(cross(b-a,c-a)/len(b-a));
}
bool online(point p,point a,point b)
{
    return sgn(cross(p-a,b-a))==0&&sgn(dot(p-a,p-b))<=0;
}
int v;
int n;
point p[50010],ch[100010];
void convex_hull()
{
    sort(p,p+n);
    n=unique(p,p+n)-p;
    v=0;
    for(int i=0;i<n;i++)
    {
        while(v>1&&cross(ch[v-1]-ch[v-2],p[i]-ch[v-2])<=0) v--;
        ch[v++]=p[i];
    }
    int j=v;
    for(int i=n-2;i>=0;i--)
    {
        while(v>j&&cross(ch[v-1]-ch[v-2],p[i]-ch[v-2])<=0) v--;
        ch[v++]=p[i];
    }
    if(n>1) v--;
}
double ans=inf;
point anspoint[4];
void roll()
{
        int j=2,l=2,r=2; //上和左右的坐标索引值
        for(int i=0;i<v;i++)
        {
            while(sgn(fabs(cross(ch[i]-ch[i+1],ch[j]-ch[i+1]))-fabs(cross(ch[i]-ch[i+1],ch[j+1]-ch[i+1])))<0)
                j=(j+1)%v;
            while(sgn(dot(ch[i+1]-ch[i],ch[r]-ch[i])-dot(ch[i+1]-ch[i],ch[r+1]-ch[i]))<0)
                r=(r+1)%v;
            while(sgn(dot(ch[i+1]-ch[i],ch[l]-ch[i])-dot(ch[i+1]-ch[i],ch[l+1]-ch[i]))>0)
                l=(l+1)%v;
            point rr=touyin(ch[r],ch[i],ch[i+1]);
            if(online(rr,ch[i],ch[i+1])) rr=ch[i+1];
            point ll=touyin(ch[l],ch[i+1],ch[i]);
            if(online(ll,ch[i+1],ch[i])) ll=ch[i];
            double h=diantoxian(rr,ll,ch[j]);
            double s=dis(ll,rr)*h;
            if(s<ans)
            {
                ans=s;
                vec temp=rotate_vec(rr-ll)/len(rr-ll)*h;
                anspoint[0]=ll;
                anspoint[1]=rr;
                anspoint[2]=rr+temp;
                anspoint[3]=ll+temp;
            }
        }
}
int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        scanf("%lf%lf",&p[i].x,&p[i].y);
    }
    convex_hull();
    roll();
    int pos=0;
    for(int i=1;i<4;i++)
    {
        if(sgn(anspoint[i].y-anspoint[pos].y)<0||(sgn(anspoint[i].y-anspoint[pos].y)==0&&sgn(anspoint[i].x-anspoint[pos].x)<0)) pos=i;
    }
    printf("%.5f\n",ans);
    for(int i=0;i<4;i++)
    {
        printf("%.5f %.5f\n",anspoint[(pos+i)%4].x,anspoint[(pos+i)%4].y);
    }
    return 0;
}

裂开了

2022/7/9 03:36
加载中...