Cod sursa(job #1826715)

Utilizator TudoseSanzianaTudose Sanziana TudoseSanziana Data 10 decembrie 2016 19:59:18
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
#include <cstdio>
#include <algorithm>
using namespace std;
const double eps=1e-12;
#define x first
#define y second
typedef pair<double,double> POINT;
int n;
POINT v[120005];
bool viz[120005];
int st[120005],top;
double cross_product(POINT P1,POINT P2,POINT P3)
{
    return (P2.x-P1.x)*(P3.y-P1.y)-(P2.y-P1.y)*(P3.x-P1.x);
}
int main()
{
    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);
    int i,p;
    scanf("%d",&n);
    for(i=1; i<=n; i++)
        scanf("%lf%lf",&v[i].x,&v[i].y);
    sort(v+1,v+n+1);
    st[++top]=1;
    st[++top]=2;
    viz[2]=1;
    for(i=1, p=1; i>0; i+=(p=(i==n?-p:p)))
        if(!viz[i])
        {
            while(top>=2 && cross_product(v[st[top-1]],v[st[top]],v[i])<eps)
                viz[st[top--]]=0;
            st[++top]=i;
            viz[i]=1;
        }
    top--;
    printf("%d\n",top);
    for(i=1; i<=top; i++)
        printf("%.6f %.6f\n",v[st[i]].x,v[st[i]].y);
    return 0;
}