Cod sursa(job #883062)

Utilizator assa98Andrei Stanciu assa98 Data 19 februarie 2013 18:21:15
Problema Infasuratoare convexa Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.22 kb
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;

struct punct
{
    double x;
    double y;
}v[120100];

punct st[120100];

bool cmp(punct a,punct b)
{
    return atan2(a.y-v[1].y,a.x-v[1].x)<atan2(b.y-v[1].y,b.x-v[1].x);
}

double det(punct a[3])
{
    double sum=0.0;
    for(int i=0;i<3;i++)
    {
        sum+=a[i].x*a[(i+1)%3].y;
        sum-=a[(i+1)%3].x*a[i].y;
    }
    return sum;
}

int n;
int poz;


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