Cod sursa(job #1238404)

Utilizator Eduard6421Eduard Gabriel Eduard6421 Data 6 octombrie 2014 21:38:18
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.24 kb
#include<cstdio>
#include<cmath>
#include<vector>
#include<algorithm>
#define eps 1.e-12
using namespace std;
struct POINT
{
    double x,y;
};
POINT POINTS[120005];
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(POINTS[0],P1,P2);
}
int st[120000];
int main()
{   freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);
    int n,i,top;
    scanf("%d%lf%lf",&n,&POINTS[0].x,&POINTS[0].y);
    for(i=1; i<n; ++i)
    {

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