Pagini recente » Cod sursa (job #422127) | Cod sursa (job #2391410) | Cod sursa (job #1508572) | Cod sursa (job #433186) | Cod sursa (job #3152475)
#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;
}