Pagini recente » Cod sursa (job #1805203) | Cod sursa (job #1596809) | Cod sursa (job #1438008) | Cod sursa (job #856713) | Cod sursa (job #840064)
Cod sursa(job #840064)
#include<fstream>
#include<algorithm>
#include<cmath>
#define Nmax 120010
#define Num 10000000
using namespace std;
int n, st[Nmax], viz[Nmax], k;
struct punct
{
float x;
float 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;
}
float dist (punct a, punct b)
{
return sqrt (double ((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y)));
}
float 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)
{
float d = det (a, b, c);
if (d > 0)
return 1;
else
if (d < 0)
return 2;
else
return 0;
}
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;
for (int i = 0; i < n; ++i)
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';
for (int i = 0; i < k; ++i)
{
h << p[st[i]].x << " " << p[st[i]].y << '\n';
}
h.close();
return 0;
}