Cod sursa(job #2416668)

Utilizator stelian2000Stelian Chichirim stelian2000 Data 27 aprilie 2019 20:54:35
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.76 kb
#include <bits/stdc++.h>

using namespace std;

struct pct
{
    double x,y;
}v[120010];

double det(pct p1,pct p2,pct p3)
{
    return (p1.x-p2.x)*(p1.y-p3.y)-(p1.x-p3.x)*(p1.y-p2.y);
}

int cmp(pct a,pct b)
{
    return det(v[1],a,b)>0;
}

int main()
{
    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);
    int n,l=1;
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%lf%lf",&v[i].x,&v[i].y);
    for(int i=2;i<=n;i++)
        if(v[i].x<v[1].x) swap(v[i],v[1]);
    sort(v+2,v+n+1,cmp);
    for(int i=2;i<=n;i++)
    {
        while(l>2 && det(v[i],v[l],v[l-1])>0) l--;
        v[++l]=v[i];
    }
    printf("%d\n",l);
    for(int i=1;i<=l;i++) printf("%.10f %.10f\n",v[i].x,v[i].y);
    return 0;
}