Pagini recente » Clasament lol_contest_try2 | Cod sursa (job #575046) | Cod sursa (job #644789) | Cod sursa (job #2149263) | Cod sursa (job #554047)
Cod sursa(job #554047)
#include<stdio.h>
#include<algorithm>
using namespace std;
typedef struct punct
{double x,y;};
punct p[120001];
int n,st[120001],vf;
bool cmp(punct l,punct r)
{return (l.x-p[1].x)*(r.y-p[1].y)>(r.x-p[1].x)*(l.y-p[1].y);}
void read()
{
scanf("%d ",&n);
for(int i=1;i<=n;i++)
scanf("%lf %lf",&p[i].x,&p[i].y);
}
int primul()
{int prim=1;
for(int i=1;i<=n;i++)
if(p[i].x<=p[prim].x)
if(p[i].x<p[prim].x||p[i].y<p[prim].y)
prim=i;
return prim;}
int directie(long p1, long p2, long p3)
{
return (p[p2].x-p[p1].x)*(p[p3].y-p[p1].y) > (p[p3].x-p[p1].x)*(p[p2].y-p[p1].y);
}
void solve()
{int prim=primul();
swap(p[1],p[prim]);
sort(p+2,p+1+n,cmp);
st[++vf]=1;
st[++vf]=2;
for(int i=3;i<=n;i++)
{if(directie(st[vf-1],st[vf],i))
st[++vf]=i;
else
{while(!directie(st[vf-1],st[vf],i)&&vf>=1)
vf--;
st[++vf]=i;}
}
}
void print()
{printf("%d\n",vf);
for(int i=1;i<=vf;i++)
printf("%lf %lf\n",p[st[i]].x,p[st[i]].y);}
int main()
{freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
read();
solve();
print();
return 0;}