Cod sursa(job #1643356)

Utilizator Stalone9f@yahoo.comStan George Alexandru [email protected] Data 9 martie 2016 18:37:26
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.95 kb
#include <bits/stdc++.h>
#define eps 0.000000000001
#define Nmax 120005

using namespace std;

struct Point
{
    double x,y;
    bool operator <(const Point &A) const
    {
        return (A.y-y > eps);
    }
} a[Nmax];
bool used[Nmax];
int st[Nmax],top,n;

inline bool Bad(Point A, Point B, Point C)
{
    return -(C.x-A.x)*(B.y-A.y)+(B.x-A.x)*(C.y-A.y) <= eps;
}

int main()
{
    int sign=1,i;
    ifstream cin("infasuratoare.in");
    ofstream cout("infasuratoare.out");
    cin>>n;
    for(i=1;i<=n;++i) cin>>a[i].x>>a[i].y;
    sort(a+1,a+n+1);
    st[++top]=1; st[++top]=2; used[2]=1;
    for(i=3;i;i+=sign)
    {
        if(used[i]) continue;
        while(top>=2 && Bad(a[st[top-1]],a[st[top]],a[i])) used[st[top--]]=0;
        st[++top]=i; used[i]=1;
        if(i==n) sign=-1;
    }
    cout<<top-1<<"\n";
    cout<<setprecision(10)<<fixed;
    for(i=1;i<top;++i) cout<<a[st[i]].x<<" "<<a[st[i]].y<<"\n";
    return 0;
}