Cod sursa(job #1400750)

Utilizator ArchazeyBaltatu Andrei-Mircea Archazey Data 25 martie 2015 13:48:47
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.19 kb
#include<bits/stdc++.h>
#define mp make_pair
#define PII pair<double,double>
#define fi first
#define se second
using namespace std;

const double eps=0.0000000000001;
const int NMAX=120005;

int n,st[NMAX];
PII a[NMAX];
bitset<NMAX>viz;

//reduc formula la o suma,sa fiu sigur ca nu gresesc
inline double Semn(int x,int y,int z)
{
    return (a[z].se*(a[y].fi-a[x].fi)+a[z].fi*(a[x].se-a[y].se)+a[x].se*(a[x].fi-a[y].fi)+a[x].fi*(a[y].se-a[x].se));
}

int main()
{
    int i,top=2,val=1;
    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);
    cin.sync_with_stdio(false);
    cin>>n;
    for (i=1;i<=n;i++) cin>>a[i].se>>a[i].fi;
    sort(a+1,a+n+1);
    st[1]=1;st[2]=2;
    viz[2]=1;
    for (i=3;i>0;i+=val)
        {
            if (viz[i]==1) continue;
            while (top>=2 && Semn(st[top],st[top-1],i)<eps)
                {
                    viz[st[top]]=0;
                    top--;
                }
            st[++top]=i;viz[i]=1;
            if (i==n) val=-1;
        }
    cout<<(top-1)<<"\n";
    cout<<setprecision(12)<<fixed;
    for (i=1;i<top;i++) cout<<a[st[i]].se<<" "<<a[st[i]].fi<<"\n";
    return 0;
}