Cod sursa(job #1226599)

Utilizator armandpredaPreda Armand armandpreda Data 6 septembrie 2014 13:20:55
Problema Infasuratoare convexa Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.34 kb
#include <cstdio>
#include <cmath>
#include <algorithm>

using namespace std;

const double eps=1.e-12;
const int MAX=120005;
struct POINT
{
    double x,y;
}p[MAX],ll;
int st[MAX];
void schimb(POINT a,POINT b)
{
    POINT cop;
    cop=a;a=b;b=cop;
}
int ccw(POINT P1,POINT P2 ,POINT P3)
{
    long long cp;
        cp=1ll*(P2.x-P1.x)*(P3.y-P2.y)-(P2.y-P1.y)*(P3.x-P2.x);
        if(cp)
            if(cp>0)
                return 1;
            else
                return -1;
        else
            return 0;
}
bool cmp(POINT a,POINT b)
{
    return ccw(ll,a,b)>0;
}
int main()
{
    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);
    int n,i,top;
    double tx,ty;
    scanf("%d%lf%lf",&n,&ll.x,&ll.y);
    for(i=1;i<n;++i)
    {
        scanf("%lf%lf",&tx,&ty);
        p[i].x=tx,p[i].y=ty;
        if((fabs(ty-ll.y)<eps and tx-ll.x<=-eps) or (ty-ll.y<=-eps))
            schimb(ll,p[i]);
    }
    p[0]=ll;
    sort(p+1,p+n,cmp);
    p[n]=p[0];
    st[0]=0;st[1]=1;
    top=1;
    i=2;
    while(i<=n)
        if(ccw(p[st[top-1]],p[st[top]],p[i])>0)
        {
            st[++top]=i;
            i++;
        }
        else
            --top;
    printf("%d\n",top);
    for(i=0;i<top;++i)
        printf("%.6lf %.6lf\n",p[st[i]].x,p[st[i]].y);
    return 0;
}