Pagini recente » Cod sursa (job #2577932) | Cod sursa (job #547235) | Cod sursa (job #1270244) | Cod sursa (job #1086435) | Cod sursa (job #2980589)
#include <algorithm>
#include <fstream>
#include <iomanip>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int const N = 120001;
int n;
int st[N] , l[N] , r[N] , idx[N] , ans[N];
double X[N] , Y[N];
double area(int i , int j , int k){
return X[i] * (Y[j] - Y[k]) + X[j] * (Y[k] - Y[i]) + X[k] * (Y[i] - Y[j]);
}
int main(){
fin >> n;
for(int i = 1 ; i <= n ; ++ i){
fin >> X[i] >> Y[i];
idx[i] = i;
}
sort(idx + 1 , idx + 1 + n);
int vf;
st[vf = 1] = idx[1];
for(int j = 2 ; j <= n ; ++ j){
int i = idx[j];
while(vf > 1 && area(st[vf - 1] , st[vf] , i) < 0){
--vf;
}
st[++vf] = i;
}
for(int i = 1 ; i <= vf ; ++ i)
ans[i] = st[i];
ans[0] = vf;
st[vf = 1] = idx[1];
for(int j = 2 ; j <= n ; ++ j){
int i = idx[j];
while(vf > 1 && area(st[vf - 1] , st[vf] , i) > 0){
--vf;
}
st[++vf] = i;
}
for(int i = vf - 1 ; i > 1 ; -- i)
ans[++ans[0]] = st[i];
fout << ans[0] << '\n';
for(int i = 1 ; i <= ans[0] ; ++ i){
fout << fixed << setprecision(12);
fout << X[ans[i]] << ' ' << Y[ans[i]] << '\n';
}
return 0;
}