Pagini recente » Cod sursa (job #457215) | Cod sursa (job #1910408) | Cod sursa (job #2670107) | Cod sursa (job #1416807) | Cod sursa (job #2063097)
#include <fstream>
#include <algorithm>
using namespace std;
FILE * fin=fopen("infasuratoare.in","r");
FILE * fout=fopen("infasuratoare.out","w");
struct punct
{
double x,y;
};
int n;
punct sol[120005];
inline double prodIncrucisat(punct A, punct B, punct C)
{
return (B.x - A.x) * (C.y - A.y) - (B.y - A.y) * (C.x - A.x);
}
bool comp(punct a, punct b)
{
return prodIncrucisat(sol[1],a,b) < 0;
}
void infasuratoare(punct*v, int n);
int main()
{
int i;
fscanf(fin,"%d",&n);
for (i=1;i<=n;i++)
fscanf(fin,"%lf%lf",&sol[i].x,&sol[i].y);
infasuratoare(sol,n);
return 0;
}
void infasuratoare(punct*v, int n)
{
int i, vf, poz;
punct minim, S[120005];
minim = v[1];
poz = 1;
for (i=2;i<=n;i++)
{
if (v[i].x < minim.x)
{
minim = v[i];
poz = i;
}
else if (v[i].x == minim.x && v[i].y < minim.y)
{
minim = v[i];
poz = i;
}
}
swap(v[1],v[poz]);
sort(v+2,v+1+n,comp);
S[1] = v[1];
S[2] = v[2];
vf = 2;
for (i=3;i<=n;i++)
{
while (vf >= 2 && prodIncrucisat(S[vf-1],S[vf],v[i]) > 0)
vf--;
S[++vf] = v[i];
}
fprintf(fout,"%d\n",vf);
for (i=vf;i>=1;i--)
fprintf(fout,"%.6lf %.6lf\n",S[i].x,S[i].y);
}