Cod sursa(job #1537168)

Utilizator CosminAlexCojocaruCojocaru Cosmin CosminAlexCojocaru Data 26 noiembrie 2015 23:24:00
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.34 kb
#include <fstream>
#include <iostream>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
int n,i,j,elements;
struct punct{float x,y;}v[120120],rez[120120];
int ff(punct a , punct b) {if(a.x!=b.x)
                            return a.x<b.x;
                        else
                            return a.y<b.y;
                        }
double E(punct p, punct p2, punct p3)
{
    return (p2.x - p.x) * (p3.y - p.y) - (p3.x - p.x)*(p2.y - p.y);
}

int main()
{
    f>>n;
    for(i=1;i<=n;i++)
        f>>v[i].x>>v[i].y;
    sort(v+1,v+n+1,ff);
    rez[1].x=v[1].x,rez[2].x=v[2].x,rez[1].y=v[1].y,rez[2].y=v[2].y;
    elements=2;
    for(i=3;i<=n;i++)
    {
        while(E(rez[elements-1],rez[elements],v[i])<=0 && elements>1)
            elements--;
        elements++;
        rez[elements]=v[i];
    }
    elements++;
    rez[elements]=v[n-1];
    for(i=n-2;i>=1;i--)
    {
        while(E(rez[elements-1],rez[elements],v[i])<=0 && elements>1)
            {elements--;
            //cout<<E(rez[elements-1],rez[elements],v[i])<<endl;
            }
        elements++;
        rez[elements]=v[i];
    }
    elements--;
    g<<elements<<endl;
    for(i=1;i<=elements;i++)
        g<<fixed<<setprecision(6)<<rez[i].x<<" "<<rez[i].y<<endl;
}