Pagini recente » Cod sursa (job #738344) | Cod sursa (job #2569378) | Istoria paginii runda/smenuri/clasament | Cod sursa (job #2605736) | Cod sursa (job #904915)
Cod sursa(job #904915)
#include <algorithm>
#include <fstream>
#include <iomanip>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
const double eps= 1e-12;
const int nmax= 120000;
inline double abs(double x){
if (x>=0){
return x;
}else{
return -x;
}
}
struct pt{
double x, y;
};
struct pt_cmp{
bool operator()(pt x, pt y){
if (abs(x.x-y.x)<=eps){
return x.y<y.y;
}else{
return x.x<y.x;
}
}
};
pt v[nmax+1];
double area(pt x, pt y, pt z){
return x.x*y.y+y.x*z.y+z.x*x.y-
x.x*z.y-y.x*x.y-z.x*y.y;
}
int u[nmax+1], l[nmax+1];
pt v_aux[nmax+1];
int main(){
int n;
fin>>n;
for (int i= 1; i<=n; ++i){
fin>>v[i].x>>v[i].y;
}
sort(v+1, v+n+1, pt_cmp());
u[0]= 1; u[1]= 1;
l[0]= 1; l[1]= 1;
for (int i= 2; i<=n; ++i){
while (u[0]>=2&& area(v[u[u[0]-1]], v[u[u[0]]], v[i])<eps){
--u[0];
}
++u[0]; u[u[0]]= i;
while (l[0]>=2&& area(v[l[l[0]-1]], v[l[l[0]]], v[i])>eps){
--l[0];
}
++l[0]; l[l[0]]= i;
}
for (int i= 1; i<=l[0]; ++i){
v_aux[i]= v[l[i]];
}
for (int i= u[0]-1; i>1; --i){
v_aux[l[0]+u[0]-i]= v[u[i]];
}
n= l[0]+u[0]-2;
fout<<n<<"\n";
fout<<setprecision(12)<<fixed;
for (int i= n; i>0; --i){
v[i]= v_aux[n-i+1];
fout<<v[i].x<<" "<<v[i].y<<"\n";
}
return 0;
}