Cod sursa(job #876427)

Utilizator BarracudaFMI-Alex Dobrin Barracuda Data 11 februarie 2013 20:23:51
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.45 kb
#include<cstdio>
#include<algorithm>
#include<math.h>
#include<limits.h>
#define dim 120007
using namespace std;
int stiv[dim],srt[dim],n;
double x[dim],y[dim];
int idx,PunctInitial,i;
bool cmpt(int i ,int j) {
     
    return (double)(x[i]-x[PunctInitial])*(y[j]-y[PunctInitial ]) <(double)(x[j]-x[PunctInitial])*(y[i]-y[PunctInitial ]);
}
long double unghi(int a,int b,int c)
{
    return (long 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];
}
 
int main (){
    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);
    scanf("%d",&n);
    x[0]=y[0]=10000000;
    PunctInitial=idx=0;
    for(i=1;i<=n;i++){
        scanf("%lf %lf",&x[i],&y[i]);
        if(x[i]<x[idx]  || (x[i]==x[idx]  && y[i]<y[idx]))
            idx=i;
         
    }
    PunctInitial=idx;
    for(i=1;i<=n;i++){
        if(i==PunctInitial)continue;
        srt[++srt[0]]=i;
    }
    sort(srt+1,srt+srt[0]+1,cmpt);
    stiv[0]=1;
    stiv[1]=PunctInitial;
    for(i=1;i<=srt[0];i++){
         
        if(srt[i]==PunctInitial)continue;
         
        while( stiv[0]>=2  && unghi(stiv[stiv[0]-1],stiv[stiv[0]],srt[i])>0 )
            --stiv[0];
        stiv[++stiv[0]]=srt[i];
    }
    stiv[++stiv[0]]=PunctInitial;
    printf("%d\n",stiv[0]-1);
    reverse(stiv+1,stiv+1+stiv[0]);
    for(i=1;i<=stiv[0]-1;i++)
        printf("%lf %lf\n",x[stiv[i]],y[stiv[i]]);
    return 0;
}