Cod sursa(job #1161446)

Utilizator Andrei1998Andrei Constantinescu Andrei1998 Data 31 martie 2014 11:23:29
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.29 kb
#include <fstream>
#include <iomanip>
#include <algorithm>

using namespace std;

struct punct
{
    double x;
    double y;
}v[120005];

bool ccw(punct a,punct b,punct c)
{
    return (((a.x-b.x)*(c.y-b.y)-(c.x-b.x)*(a.y-b.y))>0.0);
}

punct pivot;
bool operator<(const punct &a,const punct &b)
{
    return ccw(a,pivot,b);
}

int main()
{
    ifstream cin("infasuratoare.in");
    ofstream cout("infasuratoare.out");

    int n=0,i;
    cin>>n;

    cin>>v[1].x>>v[1].y;
    pivot=v[1];
    int unde=1;

    for(i=2;i<=n;i++)
    {
        cin>>v[i].x>>v[i].y;

        if(v[i].x<pivot.x)
            pivot=v[i],unde=i;
        else if(v[i].x==pivot.x)
            if(v[i].y<pivot.y)
                pivot=v[i],unde=i;
    }

    swap(v[unde],v[1]);

    if(n)
        sort(v+2,v+n+1);

    punct stiva[120005];
    int poz=0;

    stiva[++poz]=v[1];
    stiva[++poz]=v[2];

    for(i=3;i<n;i++)
    {
        while(poz>=2)
            if(ccw(stiva[poz-1],stiva[poz],v[i]))
                poz--;
            else
                break;
        stiva[++poz]=v[i];
    }

    cout<<poz<<fixed<<setprecision(6)<<'\n';
    for(i=1;i<=poz;i++)
        cout<<stiva[i].x<<' '<<stiva[i].y<<'\n';

    cin.close();
    cout.close();
    return 0;
}