Cod sursa(job #1335428)

Utilizator andreimdvMoldovan Andrei andreimdv Data 5 februarie 2015 15:00:22
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.51 kb
//Infasuratoare Convexa- INFOARENA
//Graham Scan- Andreimdv
#include <iostream>
#include<iomanip>
#include<algorithm>
#include<fstream>

using namespace std;

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

#define point pair<double,double>
#define x first
#define y second

pair<double,double> v[130000];
pair<double,double> st[130000];

double minn=1000000000;
int top,pos,n,i;

double cross(point a, point b, point c) //compararea unghiului polar folosind panta dreptelor ab si ac
{
    return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}

bool cmp(point a, point b)
{
    return cross(v[1],a,b)>0;
}

int main()
{
    fin>>n;
    for(i=1;i<=n;++i)
    {
        fin>>v[i].x>>v[i].y;
        if(v[i].y<minn) //cel mai de jos pct
        {
            minn=v[i].y;
            pos=i;
        }
    }
    swap(v[pos],v[1]); // cel mai de jos pct se afla pe pozitia 1;

    //ETAPA 1
    //sort dupa polar angle:
    sort(v+2,v+n+1,cmp);

    //ETAPA 2
    //Scanarea Graham
    st[1]=v[1]; //primele 2 pct
    st[2]=v[2];
    top=2;

    for(i=3;i<=n;++i)
    {
        while(cross(st[top-1],st[top],v[i])<0) //cat timp urmatorul punct reprezinta o intoarcere la dreapta, pop-uim din stiva
        {
            top--;
        }
        st[++top]=v[i]; // intoarcere la stanga, adaugam in stiva
    }

    //Afisare stiva:
    fout<<top<<'\n';
    for(i=1;i<=top;++i)
    fout<<fixed<<setprecision(6)<<st[i].x<<" "<<st[i].y<<'\n';


    return 0;
}