Pagini recente » Cod sursa (job #3202650) | Cod sursa (job #3294972) | Cod sursa (job #305384) | Cod sursa (job #3290572) | Cod sursa (job #3299511)
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
struct ura
{
double x, y;
} v[120002], stiva1[120002], stiva2[120002];
double arie(double xa, double xb, double xc, double ya, double yb, double yc)
{
/*if ((xa*yb+xb*yc+xc*ya-xc*yb-xa*yc-xb*ya)>=0)
return true;
return false;*/
return xa * yb + xb * yc + xc * ya - xc * yb - xa * yc - xb * ya;
}
bool cmp(ura a, ura b)
{
if (a.x > b.x)
return false;
else
{
if (a.x < b.x)
return true;
else
{
if (a.y < b.y)
return true;
else
return false;
}
}
}
int main()
{
int n;
f >> n;
for (int i = 1; i <= n; i++)
f >> v[i].x >> v[i].y;
sort(v + 1, v + n + 1, cmp);
ura st = v[1], dr = v[n];
int sp1 = 1;
int h = 0;
stiva1[1] = st;
for (int i = 2; i <= n; i++)
{
if (arie(st.x, dr.x, v[i].x, st.y, dr.y, v[i].y) < 0 || (v[i].x == dr.x && v[i].y == dr.y) )
{
while (sp1 > 1 && arie(stiva1[sp1 - 1].x, stiva1[sp1].x, v[i].x, stiva1[sp1 - 1].y, stiva1[sp1].y, v[i].y) < 0)
{
sp1--;
}
sp1++;
stiva1[sp1] = v[i];
}
}
h += sp1 - 1;
int sp2 = 1;
stiva2[sp2] = dr;
for (int i = n - 1; i >= 1; i--)
{
if (arie(st.x, dr.x, v[i].x, st.y, dr.y, v[i].y) > 0 || (v[i].x == st.x && v[i].y == st.y))
{
while (sp2 > 1 && arie(v[i].x, stiva2[sp2].x, stiva2[sp2 - 1].x, v[i].y, stiva2[sp2].y, stiva2[sp2 - 1].y) > 0)
{
sp2--;
}
sp2++;
stiva2[sp2] = v[i];
}
}
h += sp2 - 1;
g << h << endl;
g << setprecision(6) << fixed;
for (int i = 1; i < sp1; i++)
g << stiva1[i].x << " " << stiva1[i].y << endl;
for (int i = 1; i < sp2; i++)
g << stiva2[i].x << " " << stiva2[i].y << endl;
return 0;
}