Pagini recente » Cod sursa (job #591990) | Cod sursa (job #1476353) | Cod sursa (job #748415) | Cod sursa (job #1102038) | Cod sursa (job #842115)
Cod sursa(job #842115)
//#include<fstream>
#include<algorithm>
#include<cmath>
//#include<iomanip>
#include<cstdio>
#define Nmax 120010
#define Num 10000000
using namespace std;
int n, st[Nmax], viz[Nmax], k;
struct punct
{
double x;
double y;
} p[Nmax];
int cmp (punct a, punct b)
{
if (a.x > b.x || (a.x == b.x && a.y > b.y))
return 0;
return 1;
}
double dist (punct a, punct b)
{
return sqrt (double ((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y)));
}
double det (punct a, punct b, punct c)
{
return (a.x * b.y + b.x * c.y + c.x * a.y) - (a.y * b.x + b.y * c.x + c.y * a.x);
}
int semn (punct a, punct b, punct c)
{
double d = det (a, b, c);
if(fabs(d) < 0.0000000001)
return 0;
if (d > 0)
return 1;
else
return 2;
}
void convex ()
{
st[0] = 0;
st[1] = 1;
st[2] = 2;
viz[1] = viz[2] = 1;
int s = 1; //semn (p[0], p[1], p[2]);
k = 2;
int i = 3;
while (i < n)
{
int s1 = semn (p[st[k - 1]], p[st[k]], p[i]);
while (s != s1 && s1 != 0)
{
viz[st[k]] = 0;
--k;
s1 = semn (p[st[k - 1]], p[st[k]], p[i]);
}
++k;
st[k] = i;
viz[i] = 1;
++i;
}
--i;
while (i >= 0)
{
while (viz[i] && i >= 0)
--i;
if (i < 0)
break;
int s1 = semn (p[st[k - 1]], p[st[k]], p[i]);
while (s != s1 && s1 != 0)
{
--k;
s1 = semn (p[st[k - 1]], p[st[k]], p[i]);
}
++k;
st[k] = i;
--i;
}
}
int main()
{
//ifstream f("infasuratoare.in");
//ofstream h("infasuratoare.out");
//f >> n;
freopen ("infasuratoare.in", "r", stdin);
freopen ("infasuratoare.out", "w", stdout);
scanf ("%d", &n);
for (int i = 0; i < n; ++i)
scanf ("%lf %lf", &p[i].x, &p[i].y);
// f >> p[i].x >> p[i].y;
//f.close();
sort (p, p + n, cmp);
// for (int i = 0; i < n; ++i)
// h << p[i].x << " " << p[i].y << '\n';
// h << '\n'<< '\n';
convex ();
// h << k << '\n';
printf ("%d\n", k);
for (int i = 0; i < k; ++i)
{
printf ("%.13lf %.13lf\n", p[st[i]].x, p[st[i]].y);
//h.precision(6);
//h << p[st[i]].x << " " << p[st[i]].y << '\n';
}
// h.close();
return 0;
}