Cod sursa(job #885475)

Utilizator codrut94Ciucanu Codrin codrut94 Data 22 februarie 2013 01:49:27
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.3 kb
#include<cstdio>
#include<algorithm>
#include<math.h>
using namespace std;
#define N 120001
int n,ind[N],st[N],p;
double x[N],y[N];
bool compar(const int&a,const int&b)
{
    return (double)(x[a]-x[p])*(y[b]-y[p])<(double)(x[b]-x[p])*(y[a]-y[p]);
}
void citire()
{
    scanf("%d",&n);
    scanf("%lf%lf",&x[1],&y[1]);
    p=1;
    for(int i=2; i<=n; ++i)
    {
        scanf("%lf%lf",&x[i],&y[i]);
        if(x[i]<x[p]||(x[i]==x[p]&&y[i]<y[p]))
            p=i;
    }
    for(int i=1; i<=n; ++i)
    {
        if(i==p)
            continue;
        ind[++ind[0]]=i;
    }
}
double sens(int a,int b,int c)
{
    return (double)x[a]*y[b]+x[b]*y[c]+x[c]*y[a]-y[a]*x[b]-y[b]*x[c]-y[c]*x[a];
}
void infasuratoare()
{
    st[++st[0]]=p;
    for (int i=1; i<n; ++i)
    {
        //if (ind[i]==p)continue;
        while (st[0]-1&&sens(st[st[0]-1],st[st[0]],ind[i])>0)
            --st[0];
        st[++st[0]]=ind[i];
    }
}
void afis()
{
    printf("%d\n",st[0]);
    reverse(st+1,st+1+st[0]);
    for (int i=1; i<=st[0]; ++i)
        printf("%lf %lf\n",x[st[i]],y[st[i]]);
}
int main()
{
    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);
    citire();
    sort(ind+1,ind+1+ind[0],compar);
    infasuratoare();
    afis();
    return 0;
}