Pagini recente » Cod sursa (job #964920) | Cod sursa (job #1022686) | Cod sursa (job #635196) | Cod sursa (job #2494922) | Cod sursa (job #2980747)
#include <fstream>
#include <iomanip>
#include <algorithm>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int const N = 120001;
double const prec = 1e-12;
int 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]);
}
bool crt(int i , int j){
if(X[i] == X[j])
return Y[i] < Y[j];
return X[i] < X[j];
}
int idx[N];
int st[N] , dr[N];
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 , crt);
dr[dr[0] = 1] = idx[1];
for(int i = 2 ; i <= n ; ++ i){
while(dr[0] > 1 && area(dr[dr[0] - 1] , dr[dr[0]] , idx[i]) < 0)
--dr[0];
dr[++dr[0]] = idx[i];
}
st[st[0] = 1] = idx[1];
for(int i = 2 ; i <= n ; ++ i){
while(st[0] > 1 && area(st[st[0] - 1] , st[st[0]] , idx[i]) > 0)
--st[0];
st[++st[0]] = idx[i];
}
fout << st[0] + dr[0] - 2 << '\n';
for(int i = 1 ; i <= dr[0] ; ++ i)
fout << fixed << setprecision(12) << X[dr[i]] << ' ' << Y[dr[i]] << '\n';
for(int i = st[0] - 1 ; i > 1 ; -- i)
fout << fixed << setprecision(12) << X[st[i]] << ' ' << Y[st[i]] << '\n';
return 0;
}