Pagini recente » Cod sursa (job #645919) | Cod sursa (job #2768796) | Cod sursa (job #3173198) | Cod sursa (job #303185) | Cod sursa (job #544242)
Cod sursa(job #544242)
#include<stdio.h>
#include<algorithm>
using namespace std;
FILE *in,*out;
typedef struct punct
{
double x;
double y;
};
punct v[120002],P[120002],cont,aux;
int comp_sort(const punct a, const punct b)
{
if(a.x<b.x)
return 1;
if(a.x>b.x)
return 0;
if(a.y<b.y)
return 1;
return 0;
}
inline bool det_semn(punct b,punct a,punct c)
{
return (b.x*a.y + c.x*b.y + a.x*c.y - c.x*a.y - b.x*c.y - a.x*b.y)>=0;
}
int n,i,st[120002],pas=1,k;
bool uz[120002];
int main()
{
in=fopen("infasuratoare.in","rt");
out=fopen("infasuratoare.out","wt");
fscanf(in,"%d",&n);
for(i=1;i<=n;i++)
fscanf(in,"%lf %lf",&v[i].x,&v[i].y);
sort(v+1,v+n+1,comp_sort);
uz[2] = 1; st[1] = 1; st[2] = 2; k = 2; i = 3;
while(!uz[1])
{
while(uz[i])
{
if(i==n)
pas=-1;
i+=pas;
}
while(k>=2 && !det_semn(v[st[k-1]],v[st[k]],v[i]))
uz[st[k--]]=false;
st[++k]=i;
uz[i]=true;
}
fprintf(out,"%d\n",k-1);
for(i=1;i<=k-1;i++)
P[i]=v[st[i]];
P[k]=P[1];
for(i=2;i<=k;i++)
fprintf(out,"%.6lf %.6lf\n",P[i].x,P[i].y);
return 0;
}