Pagini recente » Cod sursa (job #1630484) | Cod sursa (job #534157) | Cod sursa (job #2495549) | Cod sursa (job #2751484) | Cod sursa (job #1833645)
#include <fstream>
using namespace std;
ifstream cin ("infasuratoare.in");
ofstream cout ("infasuratoare.out");
struct bla
{
float x,y;
} v[150010],aux;
int n,m,st[150100],viz[150101];
bool verif (int poz,bla key)
{
if(v[poz/2].y<key.y) return true;
if(v[poz/2].y==key.y)
{
if(v[poz/2].x<key.x) return true;
}
return false;
}
void climb (int poz)
{
bla key=v[poz];
while(3>2)
{
if(verif(poz,key) && poz>1)
v[poz]=v[poz/2],poz/=2;
else { v[poz]=key; break; }
}
}
bool verif_again (int fiu,bla key)
{
if(key.y<v[fiu].y) return true;
if(key.y==v[fiu].y)
if(key.x<v[fiu].x) return true;
return false;
}
void down (int poz)
{
bla key=v[poz];
while(3>2)
{
int fiu=0;
if(poz*2<=m) fiu=poz*2;
if(poz*2+1<=m)
{
if(v[fiu].y<v[poz*2+1].y) fiu=poz*2+1;
else if(v[fiu].y==v[poz*2+1].y && v[fiu].x<v[poz*2+1].x) fiu=poz*2+1;
}
if(fiu!=0 && verif_again(fiu,key))
v[poz]=v[fiu],poz=fiu;
else { v[poz]=key; break; }
}
}
void read ()
{
cin>>n;
for(int i=1;i<=n;i++)
cin>>v[i].x>>v[i].y,climb(i);
for(int i=n;i>1;i--)
{ m=i-1;
swap(v[i],v[1]); down(1);
}
}
bool este_naspa (bla first,bla second,bla cursed_one)
{
double rez=first.x*second.y;
rez=rez+second.x*cursed_one.y;
rez=rez+cursed_one.x*first.y;
rez=rez-cursed_one.x*second.y;
rez=rez-first.x*cursed_one.y;
rez=rez-second.x*first.y;
if(rez>=0) return true;
return false;
}
void convex ()
{
int pi=2,urm=3,unde=1;
st[1]=1; st[2]=2;
while(viz[1]==0)
{
while(viz[urm]!=0)
{
if(urm==n) unde=-1; urm+=unde;
}
while(pi>=2 && este_naspa(v[st[pi]],v[st[pi-1]],v[urm]))
viz[st[pi]]=0,pi--;
st[++pi]=urm;
viz[st[pi]]=1;
} --pi;
cout<<pi<<"\n";
for(int i=1;i<=pi;++i)
cout<<v[st[i]].x<<" "<<v[st[i]].y<<"\n";
}
int main()
{
read();
convex();
cin.close();
cout.close();
return 0;
}