bzoj 1069 [SCOI2007]最大土地面积——旋转卡壳

分手后的思念是犯贱 2021-12-20 19:59 232阅读 0赞

题目：[https://www.lydsy.com/JudgeOnline/problem.php?id=1069][https_www.lydsy.com_JudgeOnline_problem.php_id_1069]

发现 n 可以 n^2 。所以枚举对角线，分开的两部分三角形就可以旋转卡壳了。

注意坐标是实数。忘了改生成函数调了 2h+ ……

也不知道用不用管凸包上只有 3 个点的情况。反正这样的话就是枚举一个凹进去的三角形的最小面积罢了。

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    #define db double
    using namespace std;
    const int N=2005; const db INF=4e10+5;
    int n,tot,sta[N],top;db ans;
    struct Node{
      db x,y;
      Node(db a=0,db b=0):x(a),y(b) {}///db!!!!!!
      bool operator< (const Node &b)const
      {
         return x<b.x||(x==b.x&&y<b.y);}
      Node operator- (const Node &b)const
      {
         return Node(x-b.x,y-b.y);}
    }t[N],a[N];
    db Mx(db a,db b){
         return a>b?a:b;}
    db Mn(db a,db b){
         return a<b?a:b;}
    db cross(Node u,Node v){
         return u.x*v.y-u.y*v.x;}
    void get_hl()
    {
      sort(t+1,t+tot+1);
      for(int i=1;i<=tot;i++)
        {
          while(top>1&&cross(t[sta[top]]-t[i],t[sta[top-1]]-t[i])>=0)
        top--;
          sta[++top]=i;
        }
      for(int i=tot-1,lm=top;i;i--)
        {
          while(top>lm&&cross(t[sta[top]]-t[i],t[sta[top-1]]-t[i])>=0)
        top--;
          sta[++top]=i;
        }
      n=top-1;
      for(int i=1;i<=n;i++)a[i]=t[sta[i]];
    }
    void upd(int &x){
        if(x>n)x-=n;if(x<=0)x+=n;}
    void rtc(int st)
    {
      int p0=st+1,p1=st+3;upd(p1);
      a[n+1]=a[1];//
      for(int cr=st+2;cr<=n;cr++)//<=n is ok not !=(st-1)
        {
          Node d=a[cr]-a[st];
          while(cross(a[p0+1]-a[st],d)>cross(a[p0]-a[st],d))p0++,upd(p0);
          while(cross(d,a[p1+1]-a[st])>cross(d,a[p1]-a[st]))p1++,upd(p1);
          ans=Mx(ans,cross(a[p0]-a[st],d)+cross(d,a[p1]-a[st]));
        }
    }
    int main()
    {
      scanf("%d",&tot);
      for(int i=1;i<=tot;i++)scanf("%lf%lf",&t[i].x,&t[i].y);
      get_hl();
      if(n>=4)
        {
          for(int i=1,j=n-2;i<=j;i++)rtc(i);//<=n-2 is ok
          printf("%.3f\n",ans/2);
        }
      else
        {
          ans=INF;bool flag=0;
          for(int i=1;i<=n;i++)
        {
          flag=0;
          for(int j=1;j<=3;j++)
            if(t[i].x==a[j].x&&t[i].y==a[j].y)
              {flag=1;break;}
          if(flag)continue;
          ans=Mn(ans,cross(t[i]-a[1],t[i]-a[2]));
          ans=Mn(ans,cross(t[i]-a[2],t[i]-a[3]));
          ans=Mn(ans,cross(t[i]-a[3],t[i]-a[1]));
        }
          printf("%.3f\n",(cross(a[2]-a[1],a[3]-a[1])-ans)/2);
        }
      return 0;
    }

转载于:https://www.cnblogs.com/Narh/p/10146382.html

[https_www.lydsy.com_JudgeOnline_problem.php_id_1069]: https://www.lydsy.com/JudgeOnline/problem.php?id=1069