Cod sursa(job #953334)

Utilizator Andrei1998Andrei Constantinescu Andrei1998 Data 25 mai 2013 19:16:53
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.39 kb
#include <fstream>
#include <iomanip>
#include <algorithm>

using namespace std;

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

bool cp(punct a,punct b,punct c)
{
    return ((((a.x*b.y)+(b.x*c.y)+(c.x*a.y))-((c.x*b.y)+(b.x*a.y)+(a.x*c.y)))>0);
}

punct suport;

bool operator<(const punct &a,const punct &b)
{
    return cp(suport,a,b);
}

#define inf 1000000005.0

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

    double min_x=inf,min_y=inf;
    int n,i;

    fin>>n;
    for(i=0;i<n;i++)
    {
      fin>>v[i].x>>v[i].y;
      if(v[i].y<min_y)
      {
         min_y=v[i].y;
         min_x=v[i].x;
      }
      else if(v[i].y==min_y)
          if(v[i].x<min_x)
              min_x=v[i].x;
    }

    suport.x=min_x;
    suport.y=min_y;
    sort(v,v+n);
    punct stiva[120005];
    int poz=2;
/*
    for(i=0;i<n;i++)
        cout<<v[i].nume<<'\n';
*/
    stiva[0]=v[0];
    stiva[1]=v[1];
    //cout<<v[n-1].nume<<"asdasd"<<endl;

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

    fout<<poz<<'\n';
    fout<<fixed<<setprecision(6);
    for(i=0;i<poz;i++)
    {
       fout<<stiva[i].x<<' '<<stiva[i].y<<'\n';
    }

    return 0;
}