Pagini recente » Cod sursa (job #1176698) | Cod sursa (job #791817) | Cod sursa (job #2483129) | Cod sursa (job #1617285) | Cod sursa (job #538532)
Cod sursa(job #538532)
#include <stdio.h>
#include <algorithm>
#define N 120001
using namespace std;
typedef struct {double x,y;} PUNCT;
long long n,i,s,p;
PUNCT A[N],S[N],P[N];
FILE *f,*g;
bool operator < (const PUNCT &a, const PUNCT &b)
{
if (a.y<b.y)
return 1;
else if (a.y==b.y)
if (a.x<b.x)
return 1;
return 0;
}
int stanga(PUNCT a, PUNCT b, PUNCT c)
{
float st;
st=a.x*b.y+b.x*c.y+c.x*a.y-a.y*b.x-b.y*c.x-a.x*c.y;
if (st>0)
return 1;
else
return 0;
}
int main()
{
f=fopen("infasuratoare.in","r");
g=fopen("infasuratoare.out","w");
fscanf(f,"%lld",&n);
for (i=1;i<=n;++i)
fscanf(f,"%lf %lf",&A[i].x,&A[i].y);
sort(A+1,A+n+1);
s=2;
S[1]=A[1];
S[2]=A[2];
i=3;
while (i<=n)
if (stanga(S[s-1],S[s],A[i]))
{
S[++s]=A[i];
i++;
}
else
{
s--;
if (s<2)
{
S[++s]=A[i];
i++;
}
}
P[1]=A[n];
P[2]=A[n-1];
p=2;
i=n-2;
while (i>=1)
{
if (stanga(P[p-1],P[p],A[i]))
{
P[++p]=A[i];
i--;
}
else
{
p--;
if (p<2)
{
P[++p]=A[i];
p--;
}
}
}
if (n==3)
fprintf(g,"%d\n",3);
else
fprintf(g,"%lld\n",s+p-2);
for (i=1;i<=s;++i)
fprintf(g,"%.6lf %.6lf\n",S[i].x,S[i].y);
for (i=2;i<p;++i)
fprintf(g,"%.6lf %.6lf\n",P[i].x,P[i].y);
fclose(f);
fclose(g);
return 0;
}