Pagini recente » Cod sursa (job #537934) | Cod sursa (job #2748865) | Cod sursa (job #1382195) | Cod sursa (job #3270798) | Cod sursa (job #1651181)
#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];
unsigned int st[w];
double eps=1e-12;
bool viz[w];
int main()
{
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
int n,i,j,vf,k,l;double x,y;
f>>n;
for (i=1;i<=n;i++)
{
f>>x>>y;
v[i]=make_pair(x,y);
}
sort(v+1,v+n+1);
st[1]=1;st[2]=2;vf=2;
i=0;j=1;viz[2]=1;
do
{
if (i==n) j=-j;
i+=j;
if (viz[i]) continue;
{
l=st[vf-1];k=st[vf];
while (vf>=2 && det(v[l],v[k],v[i])<eps)
{
viz[k]=0;
vf--;
l=st[vf-1];k=st[vf];
}
st[++vf]=i;viz[i]=1;
}
}
while (i>0);
g<<--vf<<'\n';
g<<setprecision(6)<<fixed;
for (i=1;i<=vf;i++)
{
g<<v[st[i]].x<<' '<<v[st[i]].y<<'\n';
}
f.close();
g.close();
return 0;
}