Cod sursa(job #2535654)

Utilizator elenaisaiaElena Isaia elenaisaia Data 1 februarie 2020 10:19:56
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.51 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>

using namespace std;

int n,m,q;
struct punct{
    double x,y;
    bool operator <(punct p)
    {
        if(p.x==x)
            return(y<p.y);
        return(x<p.x);
    }
};
vector<punct>v;
punct a[120003],b[120003];

void citire()
{
    ifstream fin("infasuratoare.in");
    fin>>n;
    for(int i=0;i<n;i++)
    {
        double a,b;
        punct p;
        fin>>a>>b;
        p.x=a;
        p.y=b;
        v.push_back(p);
    }
    sort(v.begin(),v.end());
}

int sens(punct a,punct b,punct c)
{
    double det;
    det=(a.x-c.x)*(b.y-c.y)-(a.y-c.y)*(b.x-c.x);
    if(det<=0)
        return 0;
    return 1;
}

void rezolvare()
{
    a[0]=v[0];
    a[1]=v[1];
    m=2;
    for(int i=2;i<n;i++)
    {
        while(m>1&&!sens(a[m-2],a[m-1],v[i]))
            m--;
        a[m++]=v[i];
    }
    b[0]=v[n-1];
    b[1]=v[n-2];
    q=2;
    for(int i=n-3;i>=0;i--)
    {
        while(q>1&&!sens(b[q-2],b[q-1],v[i]))
            q--;
        b[q++]=v[i];
    }
}

void afisare()
{
    ofstream fout("infasuratoare.out");
    fout<<m+q-2<<"\n";
    fout<<setprecision(6)<<fixed;
    for(int i=0;i<m-1;i++)
        fout<<a[i].x<<" "<<a[i].y<<"\n";
    for(int i=0;i<q-1;i++)
        fout<<b[i].x<<" "<<b[i].y<<"\n";
}

int main()
{
    citire();
    for(int i=0;i<n;i++)
        cout<<v[i].x<<" "<<v[i].y<<"\n";
    rezolvare();
    afisare();
    return 0;
}