Cod sursa(job #902548)

Utilizator starduststardust stardust Data 1 martie 2013 14:54:50
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.25 kb
#include <cstdio>
#include <algorithm>
#define maxn 120010
#define inf 1<<30
using namespace std;

double X[maxn],Y[maxn];
int IND[maxn],ST[maxn];
double xpi,ypi;
int n,pi;

bool cmp(int i,int j)
{
    return  (((double)(Y[i]-Y[pi])*(X[j]-X[pi])) > ((double)((Y[j]-Y[pi])*(X[i]-X[pi]))));
}

long double semn(int i1,int i2,int i3)
{
    return (long double)(X[i1]*Y[i2]+X[i2]*Y[i3]+X[i3]*Y[i1]-X[i3]*Y[i2]-X[i1]*Y[i3]-X[i2]*Y[i1]);

}
void read()
{
    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);

    scanf("%d",&n);
    X[0]=Y[0]=inf;
    pi=0;
    for(int i=1;i<=n;i++)
    {
        scanf("%lf %lf",&X[i],&Y[i]);
        if(X[i]<X[pi] || (X[i]==X[pi]&&Y[i]<Y[pi])) pi=i;
    }

    for(int i=1;i<=n;i++)
      if(i!=pi) IND[++IND[0]]=i;
}

void solve()
{
    sort(IND+1,IND+IND[0]+1,cmp);
    ST[++ST[0]]=pi;
    for(int i=1;i<=IND[0];i++)
    {
        if(IND[i]==pi) continue;
        while(ST[0]>2 && semn(ST[ST[0]-1],ST[ST[0]],IND[i])>0 )
          ST[0]--;
        ST[++ST[0]]=IND[i];
    }
}
int main()
{
    read();
    solve();
    printf("%d\n",ST[0]);
    for(int i=ST[0];i>=1;i--)
    {
        printf("%lf %lf\n",X[ST[i]],Y[ST[i]]);
    }


    return 0;
}