Pagini recente » Cod sursa (job #786803) | Cod sursa (job #2870648) | Cod sursa (job #829949) | Cod sursa (job #757226) | Cod sursa (job #2980563)
#include <bits/stdc++.h>
#define pdd pair<double,double>
using namespace std;
int const nmax = 120005;
int n;
pdd A[nmax];
pdd minn;
stack <pdd> st;
double semn(pdd a ,pdd b , pdd c){
return a.first * b.second + b.first * c.second + c.first * a.second - a.second * b.first - b.second * c.first - c.second * a.first;
}
bool comp(pdd a , pdd b){
return semn(minn , a , b) > 0;
}
pdd next_top(){
auto a = st.top();
st.pop();
auto b = st.top();
st.push(a);
return b;
}
int main()
{
freopen("infasuratoare.in" , "r" , stdin);
freopen("infasuratoare.out" , "w" ,stdout);
cin.tie(0)->sync_with_stdio(0);
cin.exceptions(cin.failbit);
cin >> n;
minn.first = 2e9;
minn.second = 2e9;
int minni = 0;
for(int i = 1;i <= n; ++i){
cin >> A[i].first >> A[i].second;
if(A[i].second < minn.second)
minn = A[i] , minni = i;
else if(A[i].second == minn.second && A[i].first < minn.first)
minn = A[i] , minni = i;
}
swap(A[1] , A[minni]);
sort(A + 2 , A + n + 1 , comp);
st.push(A[1]);
st.push(A[2]);
st.push(A[3]);
for(int i = 4;i <= n; ++i){
while(st.size() > 2 && semn(next_top(),st.top(),A[i]) < 0)
st.pop();
st.push(A[i]);
}
cout << st.size() << "\n";
while(!st.empty()){
cout << fixed << setprecision(8) << st.top().first << " " << st.top().second << "\n";
st.pop();
}
}