Cod sursa(job #2172077)

Utilizator andreeagoideaAndreea Goidea andreeagoidea Data 15 martie 2018 14:57:30
Problema Infasuratoare convexa Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 1.72 kb
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <fstream>

using namespace std;

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

struct punct
{
    double x, y;
    int q;
}v[120001];

int n, nrsol, nrtot;
int st[120001];

bool cmp(punct a, punct b)
{
    if(a.x<b.x)
        return true;
    if(a.x==b.x && a.y<b.y)
        return true;
    return false;
}

int stanga(int a, int b, int c)
{
    if(v[a].x*v[b].y+v[b].x*v[c].y+v[c].x*v[a].y-v[b].x*v[a].y-v[c].x*v[b].y-v[a].x*v[c].y<0)
        return 0;
    return 1;
}

void det_dreapta()
{
    st[1]=1;
    st[2]=n;
    nrsol=2;
    for(int i=2; i<n; i++)
    {
        if(stanga(1, n, i)==0)
        {
            v[i].q=1;
            while(stanga(st[nrsol-1], st[nrsol], i)==0 && nrsol>1)
               nrsol--;
            nrsol++;
            st[nrsol]=i;

        }
    }
    if(stanga(st[nrsol-1], st[nrsol], n)==0)
        nrsol--;
    nrsol++;
    st[nrsol]=n;
}

void det_stanga()
{
    st[nrtot]=1;
    for(int i=n-1; i>=1; i--)
    {
        if(v[i].q==0)
        {
            while(stanga(st[nrtot], st[nrtot-1], i) && nrtot>nrsol)
                nrtot--;
            nrtot++;
            st[nrtot]=i;
        }
    }
    if(stanga(st[nrsol-1], st[nrsol], 1))
        nrsol--;
}

void afis()
{
    fout<<nrtot-1<<"\n";
    for(int i=1; i<=nrtot-1; i++)
        fout<<fixed<<setprecision(6)<<v[st[i]].x<<" "<<v[st[i]].y<<"\n";
}

int main()
{
    fin>>n;
    for(int i=1; i<=n; i++)
    {
        fin>>v[i].x>>v[i].y;
        v[i].q=0;
    }
    sort(v+1, v+n+1, cmp);
    det_dreapta();
    nrtot=nrsol+1;
    det_stanga();
    afis();
    return 0;
}