Cod sursa(job #2756386)

Utilizator StefantimStefan Timisescu Stefantim Data 31 mai 2021 12:22:52
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.34 kb
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
int  h[10000] , top ;
const double eps=1.e-14;
struct punct
{
    double x ,y ;
}P[120005] , LL ;
double cp(punct P1, punct P2 , punct P3)
{
    return (P2.x-P1.x)*(P3.y-P2.y) - (P2.y-P1.y)*(P3.x-P2.x) ;
}
int ccw(punct P1,punct P2,punct P3)
{
    double cpp = cp(P1,P2,P3) ;
    if(fabs(cpp)<eps)
        return 0 ;
    if(cpp>eps)
        return 1;
    return -1 ;
}
bool cmp(punct P1,punct P2)
{
    int ccww;
    ccww=ccw(LL,P1,P2) ;
    return ccww==1;
}
int main()
{
    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);
    int n , i ;
    scanf("%d",&n);
    scanf("%lf %lf",&P[1].x,&P[1].y);
    for(i=2;i<=n;i++)
    {
        scanf("%lf %lf",&P[i].x,&P[i].y);
        if((P[i].y-P[1].y<=-eps)||((fabs(P[i].y-P[1].y)<eps)&&(P[i].x-P[1].x<=-eps)))
            swap(P[1],P[i]);
    }
    LL=P[1];
    sort(P+2,P+n+1,cmp);
    P[n+1]=LL;
    top = 1;
    h[top] = 1;
    h[++top]=2 ;
    i = 3;
    while(i<=n+1)
    {
        if(ccw(P[h[top-1]],P[h[top]],P[i])>0)
        {
            h[++top]=i;
            i++;
        }
        else
            top--;
    }
    printf("%d\n",top-1);
    for(i=1;i<=top-1;i++)
    {
        printf("%f %f\n",P[h[i]].x,P[h[i]].y);
    }
    return 0;
}