Cod sursa(job #1916549)

Utilizator deliabiancasuciuSuciu delia deliabiancasuciu Data 9 martie 2017 09:46:00
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.44 kb
#include <iostream>
#include<fstream>
#include<cmath>
#include<iomanip>
#include<algorithm>
using namespace std;
ifstream in ("infasuratoare.in");
ofstream out("infasuratoare.out");
struct pct
{
    double x,y;
}v[120005],p1,p2,p3,p,stiva[120005];
int vf,ymin = 100000005,n,st,sf,i,j;
double produsincrucisat (struct pct p1,struct pct p2,struct pct p3 )
{
    return ((p2.x-p1.x)*(p3.y-p1.y))-((p3.x-p1.x)*(p2.y-p1.y));
}
bool compare ( struct pct p1,struct pct p2 )
{
    double produs = ((p1.x-p.x)*(p2.y-p.y))-((p2.x-p.x)*(p1.y-p.y));
    if( produs > 0 )  return 1;
    //if( produs == 0 )
    return 0;
}
int main()
{
    in>>n;
    for(i=1;i<=n;i++)
        {
            in>>v[i].x>>v[i].y;
            if( v[i].y < ymin )
            {
                p = v[i]; ymin = v[i].y;
            }
        }
    sort(v+1,v+n+1,compare);
    /*for(i=1;i<=n;i++)
        out<<v[i].x<<" "<<v[i].y<<"\n";*/
    stiva [1] = p; vf = 2; stiva [vf] = v[2];
    for(i=3;i<=n;i++)
    {
        if (produsincrucisat(stiva[vf-1],stiva[vf],v[i]) > 0) stiva[++vf] = v[i];
        else {
            while( produsincrucisat(stiva[vf-1],stiva[vf],v[i]) < 0 && vf > 0) vf--;
            stiva[++vf] = v[i];
        }
    }
    out<<vf<<"\n";
    for(i=1;i<=vf;i++)
    {
        out<<setprecision(6)<<fixed<<stiva[i].x;
        out<<" ";
        out<<setprecision(6)<<fixed<<stiva[i].y;
        out<<"\n";
    }
    return 0;
}