Pagini recente » Cod sursa (job #3291512) | Cod sursa (job #236379) | Cod sursa (job #3294059) | Cod sursa (job #3293622) | Cod sursa (job #3293894)
#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);
jos.push_back(v[1]);
jos.push_back(v[2]);
for(int i=3; i<=n; i++)
{
while(jos.size()>=2 && atan2(jos[jos.size()-2].y-jos[jos.size()-1].y, jos[jos.size()-2].x-jos[jos.size()-1].x)>atan2(jos[jos.size()-2].y-v[i].y, jos[jos.size()-2].x-v[i].x))
jos.pop_back();
jos.push_back(v[i]);
}
sus.push_back(v[n]);
sus.push_back(v[n-1]);
for(int i=n-2; i>=1; i--)
{
while(sus.size()>=2 && atan2(sus[sus.size()-2].y-sus[sus.size()-1].y, sus[sus.size()-2].x-sus[sus.size()-1].x)>atan2(sus[sus.size()-2].y-v[i].y, sus[sus.size()-2].x-v[i].x))
sus.pop_back();
sus.push_back(v[i]);
}
cout<<jos.size()+sus.size()-2<<'\n';
for(int i=0; i<jos.size()-1; i++)
cout<<setprecision(6)<<fixed<<jos[i].x<<" "<<jos[i].y<<'\n';
for(int i=0; i<sus.size()-1; i++)
cout<<setprecision(6)<<fixed<<sus[i].x<<" "<<sus[i].y<<'\n';
return 0;
}