Cod sursa(job #2044418)

Utilizator radudurlesteanuDurlesteanu Radu Stefan radudurlesteanu Data 21 octombrie 2017 09:54:42
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.34 kb
#include <bits/stdc++.h>
using namespace std;

struct punct{
            double x,y;
            }a[120005];

int n,st[120005],top;
bool viz[120005];

ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");

inline bool cmp(punct A,punct B)
{
if (A.y==B.y) return A.x<B.x;
else return A.y<B.y;
}

inline double F(int i,int j,int p)
{
return a[p].x*(a[i].y-a[j].y)+a[p].y*(a[j].x-a[i].x)+a[i].x*a[j].y-a[j].x*a[i].y;
}

void Hill()
{
int i;
punct p;

sort(a+1,a+n+1,cmp);
st[++top]=1;
st[++top]=2;
viz[1]=viz[2]=1;

for (i=3;i<=n;++i)
    {
    p=a[i];
    while (top>=2 && F(st[top-1],st[top],i)<0) {
                                               viz[st[top]]=0;
                                               --top;
                                               }
    st[++top]=i;
    viz[i]=1;
    }

for (i=n-1;i>=1;--i)
    if (!viz[i])
    {
    while (F(st[top-1],st[top],i)<0)
        {
        viz[st[top]]=0;
        --top;
        }
    st[++top]=i;
    viz[i]=1;
    }

while (F(st[top-1],st[top],1)<0) --top;

}

int main()
{
    int i;

    fin>>n;

    for (i=1;i<=n;++i)
        fin>>a[i].x>>a[i].y;

    Hill();

    fout<<top<<'\n';
    fout<<setprecision(12)<<fixed;
    for (i=1;i<=top;++i)
        fout<<a[st[i]].x<<" "<<a[st[i]].y<<'\n';

    return 0;
}