Pagini recente » Cod sursa (job #2440449) | Cod sursa (job #2983578) | Cod sursa (job #1323412) | Cod sursa (job #2436985) | Cod sursa (job #1655760)
#include <fstream>
#include <algorithm>
#include <iomanip>
#include <vector>
#define pp pair<double,double>
#define w 120005
#define x first
#define y second
using namespace std;
inline double det(pp A,pp B,pp C)
{
return (B.x-A.x)*(C.y-A.y)-(B.y-A.y)*(C.x-A.x);
}
pp v[w];
inline bool com(pp A,pp B)
{
return (det(v[1],A,B)<0);
}
unsigned int st[w];
int main()
{
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
int n,i,vf,k=1,l;double x,y;
f>>n;
for (i=1;i<=n;i++)
{
f>>x>>y;
v[i]=make_pair(x,y);
if (v[i]<v[k]) k=i;
}
swap(v[1],v[k]);
sort(v+2,v+n+1,com);
st[1]=1;st[2]=2;vf=2;
for (i=3;i<=n;i++)
{
l=st[vf-1];k=st[vf];
while (vf>=2 && det(v[l],v[k],v[i])>0)
{
vf--;
l=st[vf-1];k=st[vf];
}
st[++vf]=i;
}
g<<vf<<'\n';
g<<setprecision(6)<<fixed;
for (i=vf;i>=1;i--)
{
g<<v[st[i]].x<<' '<<v[st[i]].y<<'\n';
}
f.close();
g.close();
return 0;
}