Pagini recente » Cod sursa (job #1795088) | Cod sursa (job #2784291) | Diferente pentru problema/popa intre reviziile 16 si 17 | Cod sursa (job #1543183) | Cod sursa (job #1999584)
#include<cstdio>
#include<fstream>
#include<algorithm>
#include<vector>
#define NMAX 120005
using namespace std;
pair <double,double> v[NMAX];
int sol[NMAX],st[NMAX];
bool viz[NMAX];
double det(pair <double,double> a,pair <double,double> b,pair <double,double> c)
{
return a.first*b.second+b.first*c.second+c.first*a.second-b.second*c.first-c.second*a.first-a.second*b.first;
}
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].first=a;
v[i].second=b;
}
sort(v+1,v+n+1);
int top=0,a,b;
for(int i=1; i<=n; ++i)
{
if(top>1)
{
while(top>1 && det(v[a],v[b],v[i])>0)
{
viz[st[top]]=0;
--top;
a=st[top-1];
b=st[top];
}
}
st[++top]=i;
viz[st[top]]=1;
a=st[top-1];
b=st[top];
}
int rez=0;
for(int i=1; i<=top; ++i)
sol[++rez]=st[i];
top=1;
st[top]=n;
for(int i=n; i>=1; --i)
{
if(!viz[i] || i==1)
{
if(top>1)
{
while(top>1 && det(v[a],v[b],v[i])>0)
{
viz[st[top]]=0;
--top;
a=st[top-1];
b=st[top];
}
}
st[++top]=i;
viz[st[top]]=1;
a=st[top-1];
b=st[top];
}
}
for(int i=2; i<top; ++i)
sol[++rez]=st[i];
cout<<rez<<'\n';
for(int i=rez; i>=1; --i)
{
cout.precision(6);
cout<<fixed<<v[sol[i]].first<<" "<<v[sol[i]].second<<'\n';
}
return 0;
}