Pagini recente » Cod sursa (job #1260298) | Cod sursa (job #2195968) | Cod sursa (job #2351685) | Cod sursa (job #331832) | Cod sursa (job #2357715)
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <bitset>
#define eps 1e-12
using namespace std;
vector <pair<double,double>> pct;
int n,s=2;
float x,y;
bitset <120005> viz;
vector <int> q;
float det(int p1 ,int p2, int p3){
return (pct[p2].first-pct[p1].first)*(pct[p3].second-pct[p1].second) - (pct[p2].second-pct[p1].second)*(pct[p3].first-pct[p1].first);
}
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
scanf("%d", &n);
for(int i=0;i<n;++i){
cin>>x>>y;
pct.push_back({x,y});
}
sort(pct.begin(),pct.end());
q.push_back(0);
q.push_back(1);
viz[1]=1;
for(int i=2;i<n;++i){
while(s>1 && det(q[s-2],q[s-1],i)<eps){
viz[q[s-1]]=0;
--s;
q.pop_back();
}
q.push_back(i);
viz[i]=1;
++s;
}
for(int i=n-2;i>=0;--i){
if(viz[i])
continue;
while(s>1 && det(q[s-2],q[s-1],i)<eps){
viz[q[s-1]]=0;
--s;
q.pop_back();
}
q.push_back(i);
viz[i]=1;
++s;
}
q.erase(q.begin());
cout<<q.size()<<"\n";
for(int i : q)
cout<<pct[i].first<<" "<<pct[i].second<<"\n";
return 0;
}