Cod sursa(job #3152475)

Utilizator poparobertpoparobert poparobert Data 25 septembrie 2023 12:29:54
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.41 kb
#include <iostream>
#include <cstdio>
#include <stack>
#include <vector>
#include <algorithm>
#include <climits>
#include <functional>
#include <iomanip>
using namespace std;
typedef double ll;
typedef pair<ll,ll> pll;
bool operator<(const pll&a,const pll&b){return a.first!=b.first?a.first<b.first:a.second<b.second;}
istream& operator>>(istream &in,pll&a){in>>a.first>>a.second;return in;}
ostream& operator<<(ostream &out,const pll&a){out<<a.first<<' '<<a.second;return out;}
void operator-=(pll &a,const pll&b){a.first-=b.first,a.second-=b.second;}
void operator+=(pll &a,const pll&b){a.first+=b.first,a.second+=b.second;}
int main()
{
    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll n;
    cin>>n;
    pll root={LLONG_MAX,LLONG_MAX};
    vector<pll> p(n);
    for(int i=0;i<n;i++)
    {
        cin>>p[i];
        swap(p[i].first,p[i].second);
        root=min(root,p[i]);
        cerr<<p[i]<<' '<<root<<'\n';
    }
    for(int i=0;i<n;i++)p[i]-=root;
    vector<pll> rez;
    function<bool(const pll&,const pll&)>comp=[&](const pll&a,const pll&b){
        if(a.first==0)return b.first==0?a.second<b.second:a.second>=0;
        if(b.first==0)return a.first==0?a.second<b.second:b.second<0;
        if(a.second*b.second<0) return a.second>b.second;
        if(a.second==0) return b.second==0?a.first<b.first:b.second<0;
        if(b.second==0) return a.second==0?a.first<b.first:a.second>0;
        return a.first*b.second!=b.first*a.second?a.first*b.second<b.first*a.second:a.first<b.first;
    };
    //function<bool(const pll&,const pll&)comp2=[&]
    sort(p.begin(),p.end(),comp);
    for(int i=0;i<n;i++)cerr<<p[i]<<'\n',p[i]+=root;
    rez.push_back(p[0]);
    if(n==1)return cout<<1<<'\n'<<rez[0].first,1;
    rez.push_back(p[1]);
    for(int i=2;i<n;i++)
    {
        p[i]-=rez[rez.size()-2];
        rez[rez.size()-1]-=rez[rez.size()-2];
        //cerr<<p[i]<<' '<<rez[rez.size()-1]<<' '<<comp(p[i],rez[rez.size()-1]);
        if(comp(p[i],rez[rez.size()-1]))rez[rez.size()-1]=p[i],rez[rez.size()-1]+=rez[rez.size()-2];
        else rez[rez.size()-1]+=rez[rez.size()-2],p[i]+=rez[rez.size()-2],rez.push_back(p[i]);
        cerr<<endl;
    }
    cout<<rez.size()<<'\n';
    for(int i=0;i<rez.size();i++)swap(rez[i].first,rez[i].second),cout<<fixed<<setprecision(6)<<rez[i]<<'\n';
	return 0;
}