Cod sursa(job #575506)

Utilizator tamas_iuliaTamas Iulia tamas_iulia Data 8 aprilie 2011 13:35:52
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.05 kb
#include <stdio.h>
#include <algorithm>
#define Nmax 120002
#define D double
using namespace std;

D x[Nmax],y[Nmax];
int ind[Nmax],St[Nmax];
int N,p;

inline int cmp(int i,int j){
    return (y[i]-y[p])*(x[j]-x[p]) > (x[i]-x[p])*(y[j]-y[p]);
}
inline int semn(int i0,int i1,int i2){
    return (y[i2]-y[i0])*(x[i1]-x[i0]) >= (x[i2]-x[i0])*(y[i1]-y[i0]);
}

int main(){
    int i;
    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);
    scanf("%d",&N);
    for(i=1;i<=N;++i) scanf("%lf%lf",&x[i],&y[i]);
    p=1;
    for(i=2;i<=N;++i)
        if( x[i]<x[p] || (x[i]==x[p] && y[i]<y[p]) )
            p=i;

    for(i=1;i<=N;++i)
        if(i!=p) ind[++ind[0]]=i;
    sort(ind+1,ind+N,cmp);

    St[St[0]=1]=p;
    for(i=1;i<N;++i){
        while( St[0]>1 && semn(St[St[0]-1],St[St[0]],ind[i]) )
            St[0]--;
        St[++St[0]]=ind[i];
    }

    printf("%d\n",St[0]);
    for(i=St[0];i>=1;--i) printf("%lf %lf\n",x[St[i]],y[St[i]]);
    fclose(stdin); fclose(stdout);
    return 0;
}