Pagini recente » Cod sursa (job #2312638) | Cod sursa (job #943206) | Cod sursa (job #2317435) | Cod sursa (job #2168857) | Cod sursa (job #834770)
Cod sursa(job #834770)
#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 -1;
else
return 0;
}
void convex ()
{
st[0] = 0;
st[1] = 1;
st[2] = 2;
viz[0] = viz[1] = viz[2] = 1;
int s = semn (p[0], p[1], p[2]);
k = 2;
int i = 3;
while (i < n)
{
int s1 = semn (p[st[k]], p[st[k - 1]], p[i]);
while (s != s1 && s1 != 0)
{
viz[st[k]] = 0;
--k;
s1 = semn (p[st[k]], p[st[k - 1]], p[i]);
}
++k;
st[k] = i;
viz[i] = 1;
++i;
}
--i;
while (i >= 0)
{
while (viz[i])
--i;
int s1 = semn (p[st[k]], p[st[k - 1]], p[i]);
while (s != s1 && s1 != 0 && i >= 0)
{
--k;
s1 = semn (p[st[k]], p[st[k - 1]], p[i]);
}
++k;
st[k] = i;
--i;
}
}
float unghi (punct a)
{
return atan(double (a.y / a.x));
}
int cmp2 (int a, int b)
{
float d1 = unghi(p[a]);
float d2 = unghi(p[b]);
if (d1 < d2)
return 1;
else
return 0;
}
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);
convex ();
h << k << '\n';
sort (st, st + k, cmp2);
for (int i = 0; i < k; ++i)
{
long long am = p[st[i]].x * Num;
h << double (am / Num);
h << " ";
am = p[st[i]].y * Num;
h << double (am / Num);
h << '\n';
//h << p[st[i]].x << " " << p[st[i]].y << '\n';
}
//for (int i = 0; i < n; ++i)
// h << p[i].x << " " << p[i].y << '\n';
h.close();
return 0;
}