Pagini recente » Cod sursa (job #2437706) | Cod sursa (job #1545383) | Cod sursa (job #533285) | Cod sursa (job #854234) | Cod sursa (job #2280013)
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("infasuratoare.in");
FILE * fout=fopen("infasuratoare.out","w");
struct punct
{
double x, y;
};
int n, pozmin, vf;
double minim=1000000001;
punct S[120005], p[120005];
inline double modul(double x)
{
if (x < 0)
return -x;
return x;
}
double prodIncrucisat(punct A, punct B, punct C)
{
return (A.x-C.x)*(B.y-C.y)-(B.x-C.x)*(A.y-C.y);
}
bool comp(punct A, punct B)
{
double xa, ya, xb, yb, t1, t2, r1, r2;
xa = A.x-p[1].x;
ya = A.y-p[1].y;
xb = B.x-p[1].x;
yb = B.y-p[1].y;
if (xa == 0 && xb == 0)
{
if (ya*yb < 0)
return ya<yb;
return ya*ya<yb*yb;
}
if (xa == 0 && ya < 0)
return 1;
if (xa == 0 && ya > 0)
return 0;
if (xb == 0 && yb < 0)
return 0;
if (xb == 0 && yb > 0)
return 1;
t1 = ya/xa;
t2 = yb/xb;
if (modul(t1-t2) < 0.000000001)
{
r1 = xa*xa+ya*ya;
r2 = xb*xb+yb*yb;
return r1 < r2;
}
return t1 < t2;
}
int main()
{
int i;
fin >> n;
for (i=1;i<=n;i++)
{
fin >> p[i].x >> p[i].y;
if (p[i].x < minim)
{
minim = p[i].x;
pozmin = i;
}
else if (p[i].x == minim && p[i].y < p[pozmin].y)
pozmin = i;
}
swap(p[1],p[pozmin]);
sort(p+2,p+1+n,comp);
S[1] = p[1];
S[2] = p[2];
vf = 2;
for (i=3;i<=n;i++)
{
while (vf > 2 && prodIncrucisat(S[vf-1],S[vf],p[i]) < 0)
vf--;
S[++vf] = p[i];
}
fprintf(fout,"%d\n",vf);
for (i=1;i<=vf;i++)
fprintf(fout,"%.7lf %.7lf\n",S[i].x,S[i].y);
return 0;
}