Cod sursa(job #3345683)

Utilizator aadsafafdfAlexandru Spermezist aadsafafdf Data 10 martie 2026 17:02:27
Problema Infasuratoare convexa Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.48 kb
#include <bits/stdc++.h>
using namespace std;

#ifdef LOCAL
ifstream fin("file.in");
ofstream fout("file.out");
#else // LOCAL
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
//#define fin cin
//#define fout cout
#endif // LOCAL
//#define int long long
#pragma GCC optimize("Ofast")


const int big=1e9+7;
int n,aux;
vector<pair<double,double>>ans;

int orient(pair<double,double>a,pair<double,double>b,pair<double,double>c)
{
    double aux=(b.first-a.first)*(c.second-a.second)-(c.first-a.first)*(b.second-a.second);
    if(aux>0)return 1;
    if(aux<0)return -1;
    return 0;
}


int x1,x2,Y1,y2;
pair<double,double>v[120005],low={0,2e9};//x,y

bool cmp(pair<double,double>a,pair<double,double>b)
{
    return (low.first-a.first)*(low.second-b.second)>(low.first-b.first)*(low.second-a.second);
}


signed main()//97-122
{
    fin>>n;
    for(int i=1;i<=n;++i)
    {
        fin>>v[i].first>>v[i].second;
        if(v[i].second<low.second)low=v[i];
        if(v[i].second==low.second&&v[i].first<low.first)low=v[i];
    }
    sort(v+1,v+n+1,cmp);
    v[n+1]=v[1];
    for(int i=1;i<=n+1;++i)
    {
        while(ans.size()>=2&&orient(*(ans.end()-2),*(ans.end()-1),v[i])!=1)ans.pop_back();
        ans.push_back(v[i]);
    }
    ans.pop_back();
    fout<<ans.size()<<"\n";
    for(auto i:ans)
    {
        fout<<i.first<<" "<<i.second<<"\n";
    }



    return 0;
}