Cod sursa(job #2635636)

Utilizator HannaLieb Hanna Hanna Data 15 iulie 2020 10:57:40
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.49 kb
#include <fstream>
#include <vector>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <iomanip>

using namespace std;

#define NAGY 1<<30
#define KICSI 1e-12
#define P pair<double,double>
#define x first
#define y second

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

P a={0,NAGY};
int n,k,i,j,bur,h;
//double a;
/*
struct adat
{
    double x,y,s;
};*/
/*
int has(adat a, adat b)
{
       if(a.s<b.s) return 1;
    else if(a.s==b.s && (a.x-ax)<(b.x-ax)) return 1;
    else return 0;
}*/

bool fgv1(P r, P p/*double qx,double qy,double rx,double ry,double px,double py*/)
{
    int f=0;

    double cr=(r.x-a.x)*(p.y-a.y)-(p.x-a.x)*(r.y-a.y);
/*    if(cr<0) f=-1;
    else if(cr>0) f=1;
    else f=0;*/

    return cr>KICSI;
}

bool fgv(P q, P r, P p/*double qx,double qy,double rx,double ry,double px,double py*/)
{
    int f=0;

    double cr=(r.x-q.x)*(p.y-q.y)-(p.x-q.x)*(r.y-q.y);
/*    if(cr<0) f=-1;
    else if(cr>0) f=1;
    else f=0;*/

    return cr>KICSI;
}

int main()
{
    cin>>n;
    vector<P>x(n+1);
//    x[0].s=-5;
//    ax=0;
//    ay=NAGY;

    for(i=1;i<=n;i++)
    {
        cin>>x[i].x>>x[i].y;
        if(x[i].y<a.y)
        {
            h=i;
            a=x[i];
        }
        else if(x[i].y==a.y && x[i].x<a.x)
        {
            h=i;
            a=x[i];
        }
    }

  /*  for(i=1;i<=n;++i)
    {
        if(x[i].x==ax && x[i].y==ay) x[i].s=-1;
        else if(x[i].x==ax) x[i].s=90;
        else
        {
            a=0;
            a=(double)(x[i].y-ay)/(x[i].x-ax);
            x[i].s=(double)atan(a)/3.14159265*180;
            if(x[i].s<0)
                x[i].s+=180;
        }
    }*/

    x[h]=x[1];
    x[1]=a;

    sort(x.begin()+2,x.end(),fgv1);
    x.push_back(x[1]);

   // for(auto e : x) cout<<e.x<<" "<<e.y<<"\n";

    vector<P>v(n+5);

    v[1]=x[1];
    v[2]=x[2];
    i=2;
    j=3;
    bur=2;

    for(i=3;i<=n+1;++i)
    {
        while(bur>2 && !fgv(v[bur-1],v[bur],x[i])) --bur;

        ++bur;
        v[bur]=x[i];
    }

    /*for(j=3;j<=n+1;++j)
    {
        bur++;
        i=bur-1;
        k=fgv(v[i-1].x,v[i-1].y,v[i].x,v[i].y,x[j].x,x[j].y);

        if(k==1)
        {
            i++;
            v[i].x=x[j].x;
            v[i].y=x[j].y;
        }
        else if(k==0)
        {
            v[i].x=x[j].x;
            v[i].y=x[j].y;
            bur--;
        }
        else
        {
            while(fgv(v[i-1].x,v[i-1].y,v[i].x,v[i].y,x[j].x,x[j].y)==-1)
            {
                v[i].x=x[j].x;
                v[i].y=x[j].y;
                bur--;
                i--;
            }
            while(fgv(v[i-1].x,v[i-1].y,v[i].x,v[i].y,x[j].x,x[j].y)==0)
            {
                v[i].x=x[j].x;
                v[i].y=x[j].y;
                bur--;
                i--;
            }
        }


    }*/

    /*if(fgv(v[i-1].x,v[i-1].y,v[i].x,v[i].y,v[1].x,v[1].y)==0)
    {
        v[i-1].x=x[j].x;
        v[i-1].y=x[j].y;
        bur--;
    }
{1}
    bur++;
    v[bur].x=ax;
    v[bur].y=ay;
    v[bur].h=h;
    v[bur].n=0;*/

   // cout<<bur-1<<"\n";
    /*db=0;
    for(i=1;i<bur;++i)
    if(v[i+1].n!=1) db++;
{1}
    cout<<db<<"\n";
{1}
    for(i=1;i<bur;++i)
    if(v[i+1].n!=1)
        cout<<v[i].h<<" "<<v[i+1].h<<"\n";
*/
    cout<<bur-1<<"\n";
    for(i=1;i<bur;++i) cout<<setprecision(6)<<fixed<<v[i].x<<" "<<v[i].y<<"\n";
    return 0;
}