BZOJ 1069 Luogu P4166 最大土地面积 (凸包)

题目链接: (bzoj)https://www.lydsy.com/JudgeOnline/problem.php?id=1069

(luogu)https://www.luogu.org/problemnew/show/P4166

题解: 水题，凸包极角排序之后枚举凸四边形对角线\(i,j\)然后找面积最大的点\(k\)，\(k\)随着\(i,j\)是单调的

但是有个易错点，就是双指针那个\(k\)前移的条件必须是前移后大于等于原来，如果写成大于就只有50(详见代码)

查了半天发现原因居然是: 数据里有重点! 一旦有重点就会出现\(k\)一直在重点处进不动的情况。呜呜呜好坑啊

代码

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cassert>

#include<algorithm>

#include<cmath>

using namespace std;

const double EPS = 1e-8;

int dcmp(double x) {return x<-EPS ? -1 : (x>EPS ? 1 : 0);}

struct Point

{

    double x,y;

    Point() {}

    Point(double _x,double _y) {x = _x,y = _y;}

};

bool cmpy(Point x,Point y) {return dcmp(x.y-y.y)<0 || (dcmp(x.y-y.y)==0 && dcmp(x.x-y.x)<0);}

bool cmpx(Point x,Point y) {return dcmp(x.x-y.x)<0 || (dcmp(x.x-y.x)==0 && dcmp(x.y-y.y)<0);}

typedef Point Vector;

Point operator +(Point x,Point y) {return Point(x.x+y.x,x.y+y.y);}

Point operator -(Point x,Point y) {return Point(x.x-y.x,x.y-y.y);}

Point operator *(Point x,double y) {return Point(x.x*y,x.y*y);}

Point operator /(Point x,double y) {return Point(x.x/y,x.y/y);}

double Dot(Vector x,Vector y) {return x.x*y.x+x.y*y.y;}

double Cross(Vector x,Vector y) {return x.x*y.y-x.y*y.x;}

double EuclidDist(Point x,Point y) {return sqrt((x.x-y.x)*(x.x-y.x)+(x.y-y.y)*(x.y-y.y));}

Vector rotate(Vector x,double ang) {return Vector(x.x*cos(ang)-x.y*sin(ang),x.x*sin(ang)+x.y*cos(ang));}

const int N = 2000;

Point a[N+3];

Point ch[(N<<1)+3];

int stk[N+3];

double area[N+3][N+3];

int n,tp;

bool cmp(Point x,Point y) {return dcmp(Cross(x-a[1],y-a[1]))>0;}

void Convex_Hull()

{

    for(int i=2; i<=n; i++)

    {

        if(cmpy(a[i],a[1])==true) {swap(a[i],a[1]);}

    }

    sort(a+2,a+n+1,cmp);

    stk[1] = 1; stk[2] = 2; tp = 2;

    for(int i=3; i<=n; i++)

    {

        while(dcmp(Cross(a[i]-a[stk[tp-1]],a[stk[tp]]-a[stk[tp-1]]))>0) {tp--;}

        tp++; stk[tp] = i;

    }

    for(int i=1; i<=tp; i++) ch[i] = a[stk[i]];

    for(int i=1; i<=tp; i++) ch[i+tp] = ch[i];

//  printf("chsize=%d\n",tp);

//  for(int i=1; i<=tp; i++) printf("(%lf %lf)\n",ch[i].x,ch[i].y);

}

int main()

{

    scanf("%d",&n); for(int i=1; i<=n; i++) scanf("%lf%lf",&a[i].x,&a[i].y);

    Convex_Hull();

    if(tp==3)

    {

        double ans = fabs(Cross(ch[2]-ch[1],ch[3]-ch[1]))/2.0,ans2 = 1e11;

        for(int i=1; i<=n; i++)

        {

            if(i==stk[1]||i==stk[2]||i==stk[3]) continue;

            double cur = min(min(fabs(Cross(a[i]-ch[1],ch[2]-ch[1])),fabs(Cross(a[i]-ch[2],ch[3]-ch[2]))),fabs(Cross(a[i]-ch[3],ch[1]-ch[3])))/2.0;

            ans2 = min(ans2,cur);

        }

        printf("%lf\n",ans-ans2);

        return 0;

    }

    double ans = 0.0;

    for(int i=1; i<=tp; i++)

    {

        int k = i+1;

        for(int j=i+2; j<=i+tp-2; j++)

        {

            while(k+1<j && dcmp(Cross(ch[k+1]-ch[i],ch[j]-ch[i])-Cross(ch[k]-ch[i],ch[j]-ch[i]))>=0) {k++;}

            area[i][(j-1)%tp+1] = Cross(ch[k]-ch[i],ch[j]-ch[i])/2.0;

//          printf("i%d j%d k%d %lf\n",i,j,k,area[j]);

        }

    }

    for(int i=1; i<=tp; i++)

    {

        for(int j=i+2; j<=tp; j++)

        {

            double tmp = area[i][j]+area[j][i];

//          printf("area[%d][%d]=%lf\n",i,j,area[i][j]);

//          printf("area[%d][%d]=%lf\n",j,i,area[j][i]);

            ans = max(ans,tmp);

        }

    }

    printf("%.3lf\n",ans);

    return 0;

}

巴特西

BZOJ 1069 Luogu P4166 最大土地面积 (凸包)

代码

最新文章

热门文章