Pagini recente » Cod sursa (job #1693515) | Cod sursa (job #1755929) | Cod sursa (job #108212) | Cod sursa (job #1613930) | Cod sursa (job #2339232)
#include <iostream>
#include <cstdio>
#include <vector>
#include <bitset>
#include <algorithm>
#include <iomanip>
#define eps 1e-12
using namespace std;
int n,l;
double x,y;
vector <pair<double, double>> p;
vector <int> q;
bitset <120005> viz;
double det(int p1, int p2, int p3){
return (p[p2].first-p[p1].first) * (p[p3].second-p[p1].second) - (p[p2].second-p[p1].second) * (p[p3].first-p[p1].first);
}
int main(){
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
cin>>n;
for(int i=0;i<n;++i){
cin>>x>>y;
p.push_back({x,y});
}
sort(p.begin(),p.end());
q.push_back(0);
q.push_back(1);
viz[1]=1, l=2;
for(int i=2;i<n;++i){
if(viz[i])
continue;
while(l>1 && det(q[l-2],q[l-1],i)<eps){
--l;
viz[q.back()]=0;
q.pop_back();
}
++l;
q.push_back(i);
viz[i]=1;
}
for(int i=n-1;i>=0;--i){
if(viz[i])
continue;
while(l>1 && det(q[l-2],q[l-1],i)<eps){
--l;
viz[q.back()]=0;
q.pop_back();
}
++l;
q.push_back(i);
viz[i]=1;
}
q.erase(q.begin());
cout<<l-1<<"\n";
cout<<fixed<<setprecision(6);
for(int i : q)
cout<<p[i].first<<" "<<p[i].second<<"\n";
return 0;
}