Cod sursa(job #2470482)

Utilizator adiaioanaAdia R. adiaioana Data 9 octombrie 2019 11:57:43
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.71 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");

struct chestie{
double x,y,r;
bool ok;
}p[120120];
int N, ixmn,xmin,k,ymx;
vector <chestie> v;

inline void scan();
inline void print();
bool side(chestie A, chestie B, chestie C);
bool comp(const chestie &A, const chestie &B);

int main()
{
    scan();

    p[ixmn].ok=1;
    for(int i=1; i<=N; ++i) //panta pozitiva
    {
        if(p[i].x!=p[ixmn].x)
            p[i].r=(p[i].y-p[ixmn].y)/(p[i].x-p[ixmn].x);
        else p[i].r=0;
    }

    sort(p+1, p+N+1, comp);
    p[2].ok=1;k=1;
    v.push_back(p[1]);
    v.push_back(p[2]);
    for(int i=3; i<=N; ++i)
        if(!side(v[k-1],v[k],p[i]))
        {
          v.push_back(p[i]);
          k++;
        }
        else{
            while(k>1 && side(v[k-1],v[k],p[i]))
                k--;
            v[++k]=p[i];
            }
    print();
    return 0;
}

inline void scan(){

    cin>>N;
    for(int i=1; i<=N; ++i)
    {
        cin>>p[i].x>>p[i].y;
        if( (p[i].x<xmin&& (p[i].x==xmin || p[i].y>ymx) )|| ixmn==0)
            ixmn=i, xmin=p[i].x, ymx=p[i].y;
    }
}

inline void print(){

    cout<<k+1<<'\n';
    for(int i=0; i<=k; ++i)
    {
        cout<<fixed;
        cout<<setprecision(6)<<v[i].x<<' ';
        cout<<setprecision(6)<<v[i].y<<'\n';
    }
}

bool comp(const chestie &A, const chestie &B)
{
    return (A.ok>B.ok ||(A.r<B.r||(A.r==B.r && (A.y>B.y|| (A.y==B.y && A.x<B.x)))));
}

bool side(chestie A, chestie B, chestie C)
{
    double ar=(A.x*B.y+B.x*C.y+C.x*A.y-B.y*C.x-A.x*C.y-B.x*A.y);
    return (ar<0);
}