Pagini recente » Cod sursa (job #81942) | Cod sursa (job #1571708) | Cod sursa (job #530012) | Cod sursa (job #1375175) | Cod sursa (job #1153434)
#include <stdio.h>
#include <algorithm>
#define nm 120005
#define mxy 1000000001
using namespace std;
FILE *f=fopen("infasuratoare.in","r");
FILE *g=fopen("infasuratoare.out","w");
struct p{double x;double y;};
int i,n,k,u;
p v0,v[nm],st[nm];
bool cmp(p A,p B)
{
return (v0.y-A.y)*(v0.x-B.x)<(v0.y-B.y)*(v0.x-A.x);
}
bool ung(p A,p B,p C)
{
return A.x*B.y+B.x*C.y+C.x*A.y-A.x*C.y-B.x*A.y-C.x*B.y<=0;
}
int main()
{
fscanf(f,"%d",&n); v0.x=mxy;
for(i=1;i<=n;i++)
{
fscanf(f,"%lf%lf",&v[i].x,&v[i].y);
if(v[i].x<v0.x||(v[i].x==v0.x&&v[i].y<v0.y)) {v0=v[i]; k=i;}
}
swap(v[1],v[k]); stable_sort(v+2,v+n+1,cmp);
st[0]=v0; st[1]=v[2]; u=1;
for(i=3;i<=n;i++)
{
while(ung(st[u-1],st[u],v[i])) u--;
st[++u]=v[i];
}
fprintf(g,"%d\n",u+1);
for(i=0;i<=u;i++)
fprintf(g,"%lf %lf\n",st[i].x,st[i].y);
return 0;
}