Pagini recente » Cod sursa (job #2605743) | Cod sursa (job #1905533) | Cod sursa (job #390162) | Cod sursa (job #1396561) | Cod sursa (job #3180651)
#include <fstream>
#include <vector>
#include <algorithm>
#define LD long double
using namespace std;
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
const long double E = 0.000000000001;
bool is_to_the_left(pair<LD, LD> a, pair<LD, LD> b, pair<LD, LD> c){
return (b.first - a.first) * (c.second - a.second) - (b.second - a.second) * (c.first - a.first) <= E;
}
int main(){
int n;
cin>>n;
vector<pair<LD, LD> > p(n);
for(int i=0; i<n; i++)
cin>>p[i].second>>p[i].first;
sort(p.begin(), p.end());
vector<int> st(1);
vector<bool> in_stack(n);
int sign = 1;
for(int i=1; i >= 0; i += sign){
if(i == n - 1)
sign = -1;
if(in_stack[i])
continue;
int l = st.size() - 1;
while(st.size() > 1 and !is_to_the_left(p[st[l-1]], p[st[l]], p[i]))
in_stack[st[l]] = false, st.pop_back(), l--;
st.push_back(i);
in_stack[i] = true;
}
st.pop_back();
cout<<st.size()<<'\n';
for(int i:st)
cout<<p[i].second<<" "<<p[i].first<<'\n';
return 0;
}