Cod sursa(job #2124944)

Utilizator AlexVulpoiuAlexandru Vulpoiu AlexVulpoiu Data 7 februarie 2018 19:01:16
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.95 kb
#include <cstdio>
#include <algorithm>
using namespace std;
int n,i,j;
struct punct
{
    double x,y;
}a[120001],st[120001];
double det(punct A,punct B,punct C)
{
    return A.x*B.y-A.y*B.x+B.x*C.y-B.y*C.x+C.x*A.y-C.y*A.x;
}
bool comp(punct A,punct B)
{
    if(det(a[1],A,B)>0)
        return 1;
    else
        return 0;
}
int main()
{
    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);
    scanf("%d",&n);
    j=1;
    for(i=1;i<=n;i++)
    {
        scanf("%lf%lf",&a[i].x,&a[i].y);
        if(a[i].x<a[j].x || (a[i].x==a[j].x && a[i].y<a[j].y))
            j=i;
    }
    swap(a[1],a[j]);
    sort(a+2,a+n+1,comp);
    st[1]=a[1];
    st[2]=a[2];
    j=2;
    for(i=3;i<=n;i++)
    {
        while(j>=2 && det(st[j-1],st[j],a[i])<0)
            j--;
        st[++j]=a[i];
    }
    printf("%d\n",j);
    for(i=1;i<=j;i++)
        printf("%lf %lf\n",st[i].x,st[i].y);
    return 0;
}