Cod sursa(job #2635626)

Utilizator HannaLieb Hanna Hanna Data 15 iulie 2020 09:54:01
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.96 kb
#include <fstream>
#include <vector>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <iomanip>
#include <limits>

using namespace std;

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

double ax,ay;
int n,k,i,j,bur;
double a;

struct adat
{
    double x,y,s;
};
vector<adat>x;

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;
}

int fgv(double qx,double qy,double rx,double ry,double px,double py)
{
    int f=0;

    double cr=(rx-qx)*(py-qy)-(px-qx)*(ry-qy);
    if(cr<0) f=-1;
    else if(cr>0) f=1;
    else f=0;

    return f;
}

int main()
{
    cin>>n;
    x.resize(n+1);
    x[0].s=-5;
    ax=0;
    ay=INT_MAX;

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

    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;
        }
    }

    sort(x.begin(),x.end(),has);
    x.push_back({ax,ay,-1});

    vector<adat>v;

    v.resize(n+5);
    v[1].x=ax;
    v[1].y=ay;
    v[2].x=x[2].x;
    v[2].y=x[2].y;
    i=2;
    j=3;
    bur=2;

    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;
}