Pagini recente » Cod sursa (job #230434) | Cod sursa (job #3292061) | Cod sursa (job #3292060) | Cod sursa (job #3292088) | Cod sursa (job #3293895)
#include <bits/stdc++.h>
using namespace std;
struct date
{
double x, y;
} v[120005];
vector<date>jos,sus;
double eps=1e-12;
bool cmp(date a, date b)
{
if(a.x-b.x<eps)
return a.y<b.y;
return a.x<b.x;
}
int main()
{
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
ios::sync_with_stdio(false);
cin.tie(NULL);
int n;
cin>>n;
for(int i=1; i<=n; i++)
cin>>v[i].x>>v[i].y;
sort(v+1, v+n+1, cmp);
for(int i=1; i<=n; i++)
{
while(jos.size()>=2 && (v[i].x-jos[jos.size()-2].x)*(jos[jos.size()-1].y-jos[jos.size()-2].y)-(jos[jos.size()-1].x-jos[jos.size()-2].x)*(v[i].y-jos[jos.size()-2].y)<eps)
jos.pop_back();
jos.push_back(v[i]);
}
for(int i=n; i>=1; i--)
{
while(sus.size()>=2 && (v[i].x-sus[sus.size()-2].x)*(sus[sus.size()-1].y-sus[sus.size()-2].y)-(sus[sus.size()-1].x-sus[sus.size()-2].x)*(v[i].y-sus[sus.size()-2].y)<eps)
sus.pop_back();
sus.push_back(v[i]);
}
cout<<jos.size()+sus.size()-2<<'\n';
for(int i=sus.size()-1; i>=1; i--)
cout<<setprecision(6)<<fixed<<sus[i].x<<" "<<sus[i].y<<'\n';
for(int i=jos.size()-1; i>=1; i--)
cout<<setprecision(6)<<fixed<<jos[i].x<<" "<<jos[i].y<<'\n';
return 0;
}