Pagini recente » Cod sursa (job #2686384) | Cod sursa (job #2656960) | Cod sursa (job #1139007) | Cod sursa (job #557819) | Cod sursa (job #411788)
Cod sursa(job #411788)
#include<cstdio>
#include<algorithm>
#include<bitset>
using namespace std;
#define NM 1200001
#define dd double
const double eps=(double)1e-12;
dd x[NM],y[NM];
int ind[NM],st[NM],N;
bool viz[NM];
struct inf{double x,y;}v[NM];
int compar(dd a,dd b)
{
if (a+eps<b)
return -1;
if (b+eps<a)
return 1;
return 0;
}
bool cmp(const inf &a,const inf &b)
{
int r=compar(a.x,b.x);
if (r!=0)
return r==-1;
r=compar(a.y,b.y);
return r==-1;
}
int semn(int i, int j, int k)
{
dd A=v[j].y-v[i].y,B=v[i].x-v[j].x,C=v[j].x*v[i].y-v[i].x*v[j].y;
return compar(A*v[k].x+B*v[k].y+C,0);
}
void infasuratoare()
{
viz[2]=1;
st[++st[0]]=1;
st[++st[0]]=2;
int i=3,pas=1;
while (!viz[1])
{
while (viz[i])
{
if (i==N)
pas=-1;
i+=pas;
}
while (st[0]-1 && semn(st[st[0]-1],st[st[0]],i)==-1 )
viz[st[st[0]--]]=0;
st[++st[0]]=i;
viz[i]=1;
}
}
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
scanf("%d",&N);
int i;
for (i=1; i<=N; ++i)
{
scanf("%lf%lf",&v[i].x,&v[i].y);
}
sort(v+1,v+N+1,cmp);
infasuratoare();
printf("%d\n",st[0]-1);
for (i=st[0]-1; i; --i)
printf("%lf %lf\n",v[st[i]].x,v[st[i]].y);
return 0;
}