团体程序设计天梯赛(CCCC) L3012 水果忍者 上凸或下凹的证明

团体程序设计天梯赛代码。体现代码技巧，比赛技巧。  https://github.com/congmingyige/cccc_code

 #include <cstdio>

 #include <cstdlib>

 #include <cmath>

 #include <cstring>

 #include <algorithm>

 using namespace std;

 #define ll long long

 const int maxn=1e4+;

 const int inf=1e9;

 const double eps=1e-;

 struct node

 {

     int x,y;

 }d1[maxn],d2[maxn],a[maxn];

 ll cross(node c,node a,node b)

 {

     ///两者相乘，也许大于int范围

     return 1ll*(c.y-a.y)*(c.x-b.x) - 1ll*(c.x-a.x)*(c.y-b.y);

 }

 bool cmp1(node a,node b)

 {

     ll v=cross(d1[],a,b);

     if (v==)

         return d1[].x-a.x<d1[].x-b.x;

     return v<;

 }

 bool cmp2(node a,node b)

 {

     ll v=cross(d2[],a,b);

     if (v==)

         return d2[].x-a.x<d2[].x-b.x;

     return v>;

 }

 /**

 两者在v==0处无法统一

 **/

 int main()

 {

     int n,x,ymax,ymin,i,j,ind=,m;

     double k,b;

     d1[].x=inf;

     scanf("%d",&n);

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

     {

         scanf("%d%d%d",&x,&ymax,&ymin);

         d1[i]={x,ymax},d2[i]={x,ymin};

         if (d1[i].x<d1[ind].x)

             ind=i;

     }

     if (n==)

     {

         printf("%d %d %d %d",-,ymax,,ymax);

         return ;

     }

     swap(d1[],d1[ind]);

     sort(d1+,d1+n+,cmp1); ///注意是+2(对d1[2]~d1[n]排序)

     m=;

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

     {

         while (m>= && cross(a[m],a[m-],d1[i])<=)

             m--;

         a[++m]=d1[i];

     }

     for (i=;i<=m;i++)

     {

         if (a[i].x<a[i-].x)

             break;

         k=1.0*(a[i].y-a[i-].y)/(a[i].x-a[i-].x);

         b=a[i].y-k*a[i].x;

         for (j=;j<=n;j++)

             if (k*d2[j].x+b<d2[j].y-eps)

                 break;

         if (j==n+)

         {

             printf("%d %d %d %d",a[i].x,a[i].y,a[i-].x,a[i-].y);

             return ;

         }

     }

     swap(d2[],d2[ind]);

     sort(d2+,d2+n+,cmp2);

     m=;

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

     {

         while (m>= && cross(a[m],a[m-],d2[i])>=)

             m--;

         a[++m]=d2[i];

     }

     for (i=;i<=m;i++)

     {

         if (a[i].x<a[i-].x)

             break;

         k=1.0*(a[i].y-a[i-].y)/(a[i].x-a[i-].x);

         b=a[i].y-k*a[i].x;

         for (j=;j<=n;j++)

             if (k*d1[j].x+b>d1[j].y+eps)

                 break;

         if (j==n+)

         {

             printf("%d %d %d %d",a[i].x,a[i].y,a[i-].x,a[i-].y);

             return ;

         }

     }

     return ;

 }

 /*

 4

 -1 5 3

 2 4 3

 1 5 2

 0 4 3

 */