Pagini recente » Cod sursa (job #2253258) | Cod sursa (job #406815) | Cod sursa (job #53308) | Cod sursa (job #2783023) | Cod sursa (job #2339218)
#include <iostream>
#include <bitset>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <iomanip>
#define EPSILON 1e-12
using namespace std;
vector <pair<double,double>> p;
vector <int> sol;
bitset <120005> viz;
int n;
double a,b;
double det(pair<double,double> a, pair<double,double> b, pair<double,double> c)
{
return (b.first-a.first)*(c.second-a.second)-(b.second-a.second)*(c.first-a.first);
}
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
cin>>n;
for(int i=0;i<n;++i)
{
cin>>a>>b;
p.push_back({a,b});
}
sort(p.begin(),p.end());
sol.push_back(0);
sol.push_back(1);
viz[1]=1;
int l=2;
for(int i=2;i<n;++i)
{
if(viz[i])
continue;
while(l>=2 && det(p[sol[l-2]],p[sol[l-1]],p[i])<EPSILON)
{
viz[sol[l-1]]=0;
--l;
sol.pop_back();
}
++l;
sol.push_back(i);
viz[i]=1;
}
for(int i=n-1;i>=0;--i)
{
if(viz[i])
continue;
while(l>=2 && det(p[sol[l-2]],p[sol[l-1]],p[i])<EPSILON)
{
viz[sol[l-1]]=0;
--l;
sol.pop_back();
}
++l;
sol.push_back(i);
viz[i]=1;
}
sol.erase(sol.begin());
cout<<sol.size()<<"\n";
cout<<fixed<<setprecision(6);
for(int i:sol)
cout<<p[i].first<<" "<<p[i].second<<"\n";
return 0;
}