Cod sursa(job #1834852)

Utilizator geo_furduifurdui geo geo_furdui Data 25 decembrie 2016 16:27:01
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.2 kb
#include <fstream>
#include<algorithm>
#include<iomanip>
using namespace std;
ifstream cin ("infasuratoare.in");
ofstream cout ("infasuratoare.out");
#define max 1e-12
struct bla
{
    double x,y;
} puncte[120010];
int st[120010],n,p,viz[120010];
bool sortare (bla w,bla q)
{
    if(w.x!=q.x) return w.x<q.x;
    return w.y<q.y;
}
void read ()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>puncte[i].x>>puncte[i].y;
    sort(puncte+1,puncte+n+1,sortare);
}
bool it_is (bla a,bla b,bla c)
{
    if(a.x*b.y+b.x*c.y+c.x*a.y-c.x*b.y-a.x*c.y-b.x*a.y>0) return true;
    return false;
}
void convexa ()
{
    p=2; int dir=1,urm=3;
    st[1]=1; st[2]=2; viz[2]=1;
    while(viz[1]==0)
    {
        while(viz[urm]!=0)
        {
            if(urm==n) dir=-1;
            urm+=dir;
        }
        while(it_is(puncte[st[p-1]],puncte[st[p]],puncte[urm]) && p>=2) viz[st[p--]]=0;
        st[++p]=urm; viz[urm]=1;
    }
}
void write ()
{
    cout<<p-1<<"\n";
    for(int i=1;i<p;i++)
        cout<<setprecision(12)<<fixed<<puncte[st[i]].x<<" "<<puncte[st[i]].y<<"\n";
}
int main()
{
    read();
    convexa();
    write();
    cin.close();
    cout.close();
    return 0;
}