Cod sursa(job #2402053)

Utilizator MarutBrabete Marius Stelian Marut Data 10 aprilie 2019 12:13:10
Problema Infasuratoare convexa Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.7 kb
#include<cstdio>
#include<cmath>
#include<vector>
#include<algorithm>
using namespace std;
struct POINT
{
    double x,y;
};
const double eps=1e-8;
POINT LL;
vector<POINT>v;
double cp(POINT P1, POINT P2, POINT P3)
{
    return (P3.y-P2.y)*(P2.x-P1.x) - (P3.x-P2.x)*(P2.y-P1.y);
}
int ccw(POINT P1, POINT P2, POINT P3)
{
    double cpp=cp(P1,P2,P3);
    if(fabs(cpp)<eps) return 0;
    if(cpp>eps) return 1;
    return -1;
}
bool cmp(POINT P1, POINT P2)
{
    int cccw=ccw(LL,P1,P2);
    return cccw==1;
}
int h[120005];
int main()
{
    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);
    int n;
    scanf("%d",&n);
    double x,x1,xL,yL;
    POINT temp;
    for(register int i=1;i<=n;i++)
    {
        scanf("%lf%lf",&x,&x1);
        if(i==1)
        {
            xL=x;
            yL=x1;
        }
            else
            {
                if(yL==x1&&x<xL) xL=x;
                    else if(x1<yL) 
                    {
                        xL=x;
                        yL=x1;
                    }
            }
        temp.x=x;
        temp.y=x1;
        v.push_back(temp);
    }
    LL.x=xL;
    LL.y=yL;
    sort(v.begin(),v.end(),cmp);
  //  for(register int i=0;i<=v.size();i++)
     //   printf("%lf %lf\n",v[i].x,v[i].y);
    h[1]=0;
    h[2]=1;
    int top=2,i=2;
    while(i<=n-1)
    {
        if(ccw(v[h[top-1]],v[h[top]],v[i])>0)
        {
            h[++top]=i;
            i++;
        }
            else top--;
    }
 //   for(i=1;i<=top;i++)
    //    printf("%d \n",h[i]);
    printf("%d\n",top);
    for(i=1;i<=top;i++)
        printf("%lf %lf\n",v[h[i]].x,v[h[i]].y);
    return 0;
}