Pagini recente » Cod sursa (job #711698) | Cod sursa (job #1561525) | Cod sursa (job #342881) | Cod sursa (job #913961) | Cod sursa (job #1999568)
#include<cstdio>
#include<fstream>
#include<cmath>
#include<algorithm>
#include<stack>
#include<vector>
#define eps=0.000000000001
using namespace std;
struct POINT
{
double x,y;
};
POINT v[120005],sol[120005];
int st[120005];
bool viz[120005];
bool cmp(POINT a,POINT b)
{
// double m=fabs(a.x-b.x);
if(fabs(a.y-b.y)<0.000000000001)
return a.x<b.x;
else
return a.y<b.y;
}
double det(POINT a,POINT b,POINT c)
{
return a.x*b.y+b.x*c.y+c.x*a.y-b.y*c.x-c.y*a.x-a.y*b.x;
}
int main()
{
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
int n;
cin>>n;
for(int i=1; i<=n; ++i)
{
double a,b;
cin>>a>>b;
v[i].x=a;
v[i].y=b;
}
sort(v+1,v+n+1,cmp);
int top=0;
POINT a,b;
for(int i=1; i<=n; ++i)
{
if(top>1)
{
while(top>1 && det(a,b,v[i])>0)
{
viz[st[top]]=0;
--top;
a=v[st[top-1]];
b=v[st[top]];
}
}
st[++top]=i;
viz[st[top]]=1;
a=v[st[top-1]];
b=v[st[top]];
}
int rez=0;
for(int i=1; i<=top; ++i)
sol[++rez]=v[st[i]];
top=0;
for(int i=n; i>=1; --i)
{
if(!viz[i])
{
if(top>1)
{
while(top>1 && det(a,b,v[i])>0)
{
viz[st[top]]=0;
--top;
a=v[st[top-1]];
b=v[st[top]];
}
}
st[++top]=i;
viz[st[top]]=1;
a=v[st[top-1]];
b=v[st[top]];
}
}
for(int i=1; i<=top; ++i)
sol[++rez]=v[st[i]];
cout<<rez<<'\n';
for(int i=rez; i>=1; --i)
{
cout.precision(6);
cout<<fixed<<sol[i].x<<" "<<sol[i].y<<'\n';
}
return 0;
}