Cod sursa(job #1850870)

Utilizator mariusmagureanmagurean marius mariusmagurean Data 18 ianuarie 2017 23:36:32
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.43 kb
#include<fstream>
#include<iomanip>
#include<vector>
#include<algorithm>

#define dim 120005
#define eps 1e-12

using namespace std;

struct punct
{
    double x,y;
};
punct v[dim];
bool in[dim];
int s[dim],n,h;

void citire()
{
    ifstream fin("infasuratoare.in");
    fin>>n;
    for(int i=1;i<=n;i++)
        fin>>v[i].x>>v[i].y;
    fin.close();
}

int cmp(double a, double b)
{
    if(a+eps<b)
        return 1;
    if(b+eps<a)
        return -1;
    return 0;
}

bool cmpXY(punct a, punct b)
{
    int rez=cmp(a.x,b.x);
    if(rez!=0)
        return (rez==1);
    return cmp(a.y,b.y)==1;
}

int semn(punct a, punct b, punct c)
{
    double arie=a.x*(b.y-c.y)-a.y*(b.x-c.x)+b.x*c.y-b.y*c.x;
    return cmp(arie,0);
}

void graham()
{
    int varf, alt,i;
    sort(v+1,v+n+1,cmpXY);
    s[1]=1;s[2]=2;
    in[2]=1;
    i=3;
    varf=2;
    alt=1;
    while(in[1]==0)
    {
        while(in[i]!=0)
        {
            if(i==n)
                alt=-1;
            i+=alt;
        }
        while(varf>=2 && semn(v[s[varf-1]], v[s[varf]], v[i])==-1)
        {
            in[s[varf]]=0;
            varf--;
        }
        s[++varf]=i;
        in[i]=1;
    }
    h=varf-1;
}

int main()
{
    ofstream fout("infasuratoare.out");
    citire();
    graham();
    fout<<fixed<<h<<"\n";
    for(int i=h+1;i>=2;i--)
        fout<<v[s[i]].x<<" "<<v[s[i]].y<<"\n";
    return 0;
}