Pagini recente » Cod sursa (job #361508) | Cod sursa (job #2080180) | Cod sursa (job #2475853) | Cod sursa (job #2933705) | Cod sursa (job #1881083)
#include <fstream>
#include<algorithm>
#include<iomanip>
using namespace std;
ifstream cin ("infasuratoare.in");
ofstream cout ("infasuratoare.out");
struct bla
{
double x,y;
} point[120010];
int viz[120010],st[120010],n,vf=2;
bool sortare (bla q,bla w)
{
if(q.y!=w.y) return q.y<w.y;
return q.x<w.x;
}
void read ()
{
cin>>n;
for(int i=1;i<=n;i++)
cin>>point[i].x>>point[i].y;
sort(point+1,point+1+n,sortare);
}
bool IsOkay (bla a,bla b,bla c)
{
if((c.x-a.x)*(a.y-b.y)-(a.x-b.x)*(c.y-a.y)<0) return true;
return false;
}
void convex ()
{
int next=3,where=1;
st[1]=1; st[2]=2; viz[2]=1;
while(viz[1]==0)
{
while(viz[next]!=0)
{
if(next==n) where=-1; next+=where;
}
while(vf>1 && IsOkay(point[st[vf-1]],point[st[vf]],point[next])) viz[st[vf--]]=0;
st[++vf]=next; viz[next]=1;
}
}
void write ()
{
cout<<vf-1<<"\n";
for(int i=1;i<vf;++i)
cout<<fixed<<setprecision(12)<<point[st[i]].x<<" "<<point[st[i]].y<<"\n";
}
int main()
{
read();
convex();
write();
cin.close();
cout.close();
return 0;
}