Cod sursa(job #1238415)

Utilizator Eduard6421Eduard Gabriel Eduard6421 Data 6 octombrie 2014 22:08:04
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.19 kb
#include<cstdio>
#include<cmath>
#include<vector>
#include<algorithm>
#define eps 1.e-12
using namespace std;
struct POINT
{
    double x,y;
};
POINT MPOT[120005];
int st[120000];
inline bool ccw(const POINT &P1, const POINT &P2,const POINT &P3)
{
    return (P2.x-P1.x)*(P3.y-P2.y)-(P2.y-P1.y)*(P3.x-P2.x)>0;
}
inline bool myComp (const POINT &P1, const POINT &P2)
{
    return ccw(MPOT[0],P1,P2);
}
int main()
{   freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);
    int n,i,top;
    scanf("%d%lf%lf",&n,&MPOT[0].x,&MPOT[0].y);
    for(i=1; i<n; ++i)
    {

        scanf("%lf%lf",&MPOT[i].x,&MPOT[i].y);
        if((fabs(MPOT[i].y-MPOT[0].y)<eps&&MPOT[i].x-MPOT[0].x<=-eps)||MPOT[i].y-MPOT[0].y<=-eps)
        swap(MPOT[0],MPOT[i]);
    }
    sort(MPOT+1,MPOT+n,myComp);
    MPOT[n]=MPOT[0];
    st[0]=0;
    st[1]=1;
    top=1;
    i=2;
    while(i<=n)
    {
        if(ccw(MPOT[st[top-1]],MPOT[st[top]],MPOT[i]))
        {
            st[++top]=i++;
        }
        else
            --top;
    }
    printf("%d\n",top);
    for(i=0;i<top;++i)
            printf("%lf %lf\n",MPOT[st[i]].x,MPOT[st[i]].y);
    return 0;
}