Pagini recente » Cod sursa (job #721348) | Cod sursa (job #2945724) | Cod sursa (job #351339) | Cod sursa (job #393368) | Cod sursa (job #1957948)
#include <fstream>
#include<algorithm>
#include<iomanip>
using namespace std;
ifstream cin ("infasuratoare.in");
ofstream cout ("infasuratoare.out");
int n;
struct bla
{
double x,y;
} date[150100];
int used[150100];
int st[150100];
int vf;
bool sortare (bla q,bla w)
{
if(q.x==w.x) return q.y<w.y;
return q.x<w.x;
}
void read ()
{
cin>>n;
for(int i=1;i<=n;i++)
cin>>date[i].x>>date[i].y;
sort(date+1,date+n+1,sortare);
}
int ec_dreptei (bla a,bla b,bla c)
{
return (c.x-a.x)*(a.y-b.y)-(a.x-b.x)*(c.y-a.y);
}
void convex ()
{
vf=2;
st[1]=1;
st[2]=2;
used[2]=1;
int urm=3,sens=1;
while(used[1]==0)
{
while(used[urm]!=0)
{
if(urm==n) sens=-1;
urm+=sens;
}
while(vf>1 && ec_dreptei(date[st[vf-1]],date[st[vf]],date[urm])<0) used[st[vf--]]=0;
st[++vf]=urm;
used[urm]=1;
}
}
void write ()
{
cout<<vf-1<<"\n";
for(int i=1;i<vf;i++)
{
cout<<fixed<<setprecision(12)<<date[st[i]].x<<" "<<date[st[i]].y<<"\n";
}
}
int main()
{
read();
convex();
write();
cin.close();
cout.close();
return 0;
}