Pagini recente » Cod sursa (job #3005510) | Cod sursa (job #2317723) | Cod sursa (job #888070) | Cod sursa (job #2266587) | Cod sursa (job #2144601)
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <iomanip>
#define EPSILON 1e-12
using namespace std;
vector <pair<double,double>> p;
vector <pair<double,double>> sol;
int n;
double a,b;
bool cmp(pair<double,double> a, pair<double,double> b)
{
return (a.first<b.first) || (a.first<b.first && a.second<b.second);
}
double det(pair<double,double> a, pair<double,double> b, pair<double,double> c)
{
return (a.first-b.first)*(a.second-c.second)-(a.second-b.second)*(a.first-c.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(),cmp);
sol.push_back(p[0]);
sol.push_back(p[n-1]);
int l=1;
for(int i=n-2;i>0;--i)
{
while(sol.size()>2 && det(sol[l-1],sol[l],p[i])<EPSILON)
{
--l;
sol.pop_back();
}
++l;
sol.push_back(p[i]);
}
cout<<sol.size()<<"\n";
cout<<fixed<<setprecision(6);
for(auto i:sol)
cout<<i.first<<" "<<i.second<<"\n";
return 0;
}