Pagini recente » Cod sursa (job #2032814) | Cod sursa (job #1326242) | Cod sursa (job #2365197) | Cod sursa (job #2709223) | Cod sursa (job #2921569)
#include<bits/stdc++.h>
#define int long long
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
int n,stiva[120005],viz[120005];
struct punct
{
double x,y;
}v[120005];
int cmp(punct a, punct b)
{
if(a.x==b.x)
return a.y<b.y;
return a.x<b.x;
}
double calculam(punct a, punct b, punct c)
{
if((b.y-a.y)*(c.x-a.x)>=(c.y-a.y)*(b.x-a.x))
return 1;
return 0;
}
signed main()
{
int i,prim,pas;
f>>n;
for(i=1;i<=n;i++)
f>>v[i].x>>v[i].y;
sort(v+1,v+n+1,cmp);
stiva[1]=1;
stiva[2]=2;
prim=2;
viz[2]=1;
i=3;
pas=1;
while(viz[1]==0)
{
if(viz[i]==0)
{
while(prim>=2 && calculam(v[stiva[prim-1]],v[stiva[prim]],v[i])==1)
{
viz[stiva[prim]]=0;
prim--;
}
viz[i]=1;
prim++;
stiva[prim]=i;
}
if(i==n)
pas=-1;
i+=pas;
}
prim--;
g<<prim<<'\n';
for(i=1;i<=prim;i++)
g<<fixed<<setprecision(12)<<v[stiva[i]].x<<" "<<fixed<<setprecision(12)<<v[stiva[i]].y<<'\n';
return 0;
}