Cod sursa(job #1029302)

Utilizator Andrei1998Andrei Constantinescu Andrei1998 Data 15 noiembrie 2013 12:39:11
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.39 kb
#include <fstream>
#include <iomanip>
#include <algorithm>

using namespace std;

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

double ccp(punct a,punct b,punct c)
{
    return (a.x-b.x)*(c.y-b.y)-(a.y-b.y)*(c.x-b.x);
}

punct centru;

bool operator<(const punct &a,const punct &b)
{
    return (ccp(a,centru,b)>0);
}

int main()
{
    ifstream cin("infasuratoare.in");
    ofstream cout("infasuratoare.out");
    centru.x=1000000005;
    centru.y=1000000005;
    int n=0,i,unde;
    cin>>n;
    for(i=0;i<n;i++)
    {
        cin>>v[i].x>>v[i].y;
        if(v[i].x<centru.x)
            centru=v[i],unde=i;
        else if(v[i].x==centru.x)
            if(v[i].y<centru.y)
                centru=v[i],unde=i;
    }
    swap(v[0],v[unde]);
    sort(v+1,v+n);

   // cout<<"aici"<<endl;
   // for(i=0;i<n;i++)
   // {
   //     cout<<v[i].x<<' '<<v[i].y<<endl;
   // }
    //cout<<"HJOP"<<endl;

    punct stiva[120005];
    int poz=-1;
    stiva[++poz]=v[0];
    stiva[++poz]=v[1];

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

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