Cod sursa(job #2159173)

Utilizator moltComan Calin molt Data 10 martie 2018 19:46:39
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.25 kb
#include <bits/stdc++.h>

using namespace std;

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

struct pct
{
    double x,y;
};
pct v[120001],st[120001],vv[120001];

bool cmp(pct a,pct b){
    if (a.x < b.x)
        return true;
    if (a.x == b.x)
        if (a.y < b.y)
            return true;
    return false;
}

bool semn (pct p1,pct p2,pct p3) {
    return (p2.x*p1.y+p3.x*p2.y+p1.x*p3.y-p1.x*p2.y-p2.x*p3.y-p3.x*p1.y)<0;
}

int main()
{
    int n,i,vf = 0,lf;
    in>>n;
    for (int i = 0;i < n;i++)
        in>>v[i].x >> v[i].y;
    sort(v,v + n,cmp);
    st[++vf]=v[0];
    for (i = 1;i < n;i++) {
        while (vf > 1 && !semn(st[vf-1],st[vf],v[i]))
            vf--;
        st[++vf]=v[i];
    }
    lf = vf;
    for (int i = 1;i <= vf;i++)
        vv[i]=st[i];
    vf = 0;
    st[++vf]=v[n - 1];
    for (int i = n - 2;i >= 0;i--) {
        while (vf > 1 && !semn(st[vf-1],st[vf],v[i]))
            vf--;
        st[++vf]=v[i];
    }
    for (int i = 2;i <= vf;i++)
        vv[i+lf-1] = st[i];
    lf = lf + vf - 2;
    out<<lf<<"\n";
    out<<fixed<<setprecision(6);
    for(int i = 2;i <= lf;i++)
        out<<vv[i].x<<" "<<vv[i].y<<"\n";
    out<<vv[1].x<<" "<<vv[1].y;
    return 0;
}