Pagini recente » Cod sursa (job #1132350) | Cod sursa (job #1499516) | Cod sursa (job #654732) | Cod sursa (job #2857356) | Cod sursa (job #2310909)
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
const double eps = 1.e-12;
struct Points
{
double x,y;
};
Points v[120005];
Points sol[120005];
int st[120005];
double det(Points P1, Points P2, Points P3)
{
return (P2.x-P1.x)*(P3.y-P1.y)-(P2.y-P1.y)*(P3.x-P1.x);
}
bool cmp1(Points P1, Points P2)
{
if(fabs(P1.x-P2.x)<eps)
return P1.y-P2.y<eps;
return P1.x-P2.x<eps;
}
bool cmp2(Points P1, Points P2)
{
if(fabs(P1.x-P2.x)<eps)
return P1.y-P2.y>eps;
return P1.x-P2.x<eps;
}
int main()
{ freopen("infasuratoare.in", "r",stdin);
freopen("infasuratoare.out", "w",stdout);
int n,i,top,nr,ok=0,ii,minx=2000000000,miny=2000000000;
scanf("%d", &n);
for(i=1; i<=n; i++)
scanf("%lf%lf", &v[i].x, &v[i].y);
sort(v+1, v+n+1,cmp1);
st[1]=1;
st[2]=2;
top=2;
double x=det(v[1], v[2], v[3]);
for(i=3; i<=n; i++){
while(top>=2 && det(v[st[top-1]], v[st[top]], v[i])<eps)
top--;
st[++top]=i;
}
for(i=1; i<=top; i++)
sol[i]=v[st[i]];
nr=top;
sort(v+1, v+n+1,cmp2);
st[1]=1;
st[2]=2;
top=2;
for(i=3; i<=n; i++){
while(top>=2 && det(v[st[top-1]], v[st[top]], v[i])>eps)
top--;
st[++top]=i;
}
reverse(st+1, st+top+1);
if(fabs(v[n].x-v[n-1].x)<eps)
ok=2;
if(v[2].x-v[1].x>eps)
ok++;
if(v[n].x-v[n-1].x>eps)
ok++;
printf("%d\n", nr+top-ok);
for(i=1; i<=nr; i++){
if(sol[i].y<miny){
miny=sol[i].y;
minx=sol[i].x;
ii=i;
}
else
if(sol[i].y==miny){
if(sol[i].x<minx){
minx=sol[i].x;
ii=i;
}
}
}
for(i=ii; i<=nr; i++)
printf("%lf %lf\n", sol[i].x, sol[i].y);
i=1;
if(fabs(v[n].x-v[n-1].x)<eps)
i+=2;
else
i++;
for(; i<top; i++)
printf("%lf %lf\n", v[st[i]].x, v[st[i]].y);
if(fabs(v[2].x-v[1].x)<eps)
printf("%lf %lf\n", v[st[i]].x, v[st[i]].y);
for(i=1; i<ii; i++)
printf("%lf %lf\n", sol[i].x, sol[i].y);
return 0;
}