Cod sursa(job #2662942)

Utilizator loraclorac lorac lorac Data 24 octombrie 2020 21:52:34
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.11 kb
#include <bits/stdc++.h>
using namespace std;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
typedef long double ld;
typedef pair<ld,ld> pdd;
const int lim=12e4+5;
#define x first
#define y second
pdd p[lim];
bool mycmp(pdd a,pdd b)
{
    return (a.y-p[1].y)*(b.x-p[1].x)<(b.y-p[1].y)*(a.x-p[1].x);
}
bool ok(pdd a,pdd b,pdd c)
{
    return (b.y-a.y)*(c.x-b.x)<(c.y-b.y)*(b.x-a.x);
}
vector<pdd> st;
int main()
{
    int n;
    in>>n;
    for(int i=1;i<=n;++i)
        in>>p[i].x>>p[i].y;
    for(int i=2;i<=n;++i)
    if(p[i].y<p[1].y or (p[i].y==p[1].y and p[i].x<p[1].x))
        swap(p[1],p[i]);
    sort(p+2,p+n+1,mycmp);
    st.push_back(p[1]);
    pdd last;
    for(int i=2;i<=n;++i)
    {
        while(st.size()>=3)
        {
            last=st.back(); st.pop_back();
            if(ok(st.back(),last,p[i]))
            {
                st.push_back(last);
                break;
            }
        }
        st.push_back(p[i]);
    }
    out<<st.size()<<'\n';
    for(pdd a:st)
        out<<fixed<<setprecision(8)<<a.x<<' '<<a.y<<'\n';
    return 0;
}