Cod sursa(job #2738280)

Utilizator betybety bety bety Data 5 aprilie 2021 17:28:52
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.08 kb
#include <bits/stdc++.h>
using namespace std;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
#define x first
#define y second
typedef long double ld;
typedef pair<ld,ld> pii;
const int lim=12e4+5;
pii v[lim];
bool mycmp(pii a,pii b)
{
    return (v[1].y-a.y)*(v[1].x-b.x)<(v[1].y-b.y)*(v[1].x-a.x);
}
vector<pii> ans;
int main()
{
    int n;
    in>>n;
    for(int i=1;i<=n;++i)
        in>>v[i].x>>v[i].y;
    pii minim=v[1];
    int unde=1;
    for(int i=2;i<=n;++i)
    if(v[i]<minim)
    {
        minim=v[i];
        unde=i;
    }
    swap(v[1],v[unde]);
    sort(v+2,v+n+1,mycmp);
    ans.push_back(v[1]);
    ans.push_back(v[2]);
    int cnt=1;
    for(int i=3;i<=n;++i)
    {
        while(ans.size()>=2 and (ans[cnt-1].y-ans[cnt].y)*(ans[cnt].x-v[i].x)>(ans[cnt].y-v[i].y)*(ans[cnt-1].x-ans[cnt].x))
            ans.pop_back(),--cnt;
        ans.push_back(v[i]);
        ++cnt;
    }
    out<<ans.size()<<'\n';
    for(int i=0;i<ans.size();++i)
        out<<fixed<<setprecision(6)<<ans[i].x<<' '<<ans[i].y<<'\n';
    return 0;
}