Pagini recente » Cod sursa (job #1544642) | Cod sursa (job #1290887) | Cod sursa (job #2557568) | Cod sursa (job #442718) | Cod sursa (job #2000007)
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <vector>
using namespace std;
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
pair<double, double> A[120005];
int under[120005];
int top[120005];
bool used[120005];
long long det(pair<int, int> a1, pair<int, int> a2, pair<int, int> a3){
return a1.second*a2.first + a2.second*a3.first + a3.second*a1.first - a2.first*a3.second - a3.first*a1.second - a1.first*a2.second;
}
int main()
{
int n;
cin>>n;
for ( int i=1; i<=n; i++ ){
double x, y;
cin>>x;
cin>>y;
A[i].first=y;
A[i].second=x;
}
sort(A+1, A+n+1);
int contdown=0;
int last, beflast;
for (int i=1; i<=n; i++){
if (contdown > 1){
while (contdown > 1 && det(A[beflast], A[last], A[i])> 0){
contdown--;
used[last]=0;
last=under[contdown];
beflast=under[contdown-1];
}
}
contdown++;
under[contdown]=i;
beflast=last;
last=i;
if (i!=1 && i!=n){
used[i]=1;
}
}
//am facut partea de jos
int contup=0;
for (int i=n; i>=1; i--){
if (used[i] == 1){
continue;
}
if (contup > 1){
while (contup > 1 && det(A[beflast], A[last], A[i])> 0){
contup--;
last=top[contup];
beflast=top[contup-1];
}
}
contup++;
top[contup]=i;
beflast=last;
last=i;
}
//am facut partea de sus
cout<<contdown+contup-2<<'\n';
for (int i=contup; i>1; i--){
cout<<setprecision(6)<<fixed<<A[top[i]].second<<" "<<A[top[i]].first<<'\n';
}
for (int i=contdown; i>1; i--){
cout<<setprecision(6)<<fixed<<A[under[i]].second<<" "<<A[under[i]].first<<'\n';
}
return 0;
}