Cod sursa(job #2470841)

Utilizator adiaioanaAdia R. adiaioana Data 9 octombrie 2019 19:57:11
Problema Infasuratoare convexa Scor 30
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;
}p[120120], ps;
int N, ixmn,ymin,k,xmn;
vector <chestie> v;

bool operator ==(const chestie &A, const chestie &B)
{
    return (A.x==A.y && B.x==B.y);
}
inline void scan();
double r(chestie X);
inline void print();
bool notsoclockwise(chestie A, chestie B, chestie C);
bool comp(const chestie &A, const chestie &B);

int main()
{
    scan();

    sort(p+1, p+N+1, comp);
    k=2;
    v.push_back(p[1]);
    v.push_back(p[2]);
    for(int i=3; i<=N; ++i){

        while(k>1 && notsoclockwise(v[k-2],v[k-1],p[i]))
        {
            v.pop_back();
            k--;
        }
        v.push_back(p[i]);
        k++;
    }
    print();
    return 0;
}

inline void scan(){

    cin>>N;
    ps.y=1000000000;
    ps.x=1000000000;
    for(int i=1; i<=N; ++i)
    {
        cin>>p[i].x>>p[i].y;
        if( (p[i].y<ps.y&& (p[i].y==ps.y || p[i].x<ps.x) ))
            ps=p[i];
    }
}

inline void print(){

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

bool comp(const chestie &A, const chestie &B)
{
    if(A==ps)
        return 1;
    if(B==ps)
        return 0;
   return (1-notsoclockwise(ps,A,B));
}

bool notsoclockwise(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);
}

double r(chestie X)
{
    if(X.y!=ymin)
        return (X.x-xmn)/(X.y-ymin);
    else return 0;
}