Pagini recente » Cod sursa (job #629281) | sandwich | Cod sursa (job #1009739) | Cod sursa (job #2296767) | Cod sursa (job #3315960)
#include <fstream>
#include <algorithm>
using namespace std;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
struct punct
{
double x, y;
}v[120001], j[120001], s[120001], st[120001], drum[120001];
bool cmp(punct a, punct b)
{
if (a.x < b.x)
return true;
else if (a.x > b.x)
return false;
else if (a.y < b.y)
return true;
else
return false;
}
double arie(double ax, double ay, double bx, double by, double cx, double cy)
{
return (ax * by + bx * cy + cx * ay - cx * by - ax * cy - bx * ay);
}
int main()
{
int n, i, nj = 0, ns = 0, c = 1;
in >> n;
for (i=1;i<=n;i++)
in >> v[i].x >> v[i].y;
sort(v, v+n+1, cmp);
drum[c].x = v[1].x;
drum[c].y = v[1].y;
for (i=2;i<n;i++)
{
if (arie(v[1].x, v[1].y, v[n].x, v[n].y, v[i].x, v[i].y) < 0)
{
nj++;
j[nj].x = v[i].x;
j[nj].y = v[i].y;
}
else
{
ns++;
s[ns].x = v[i].x;
s[ns].y = v[i].y;
}
}
int k = 2;
st[1].x = v[1].x;
st[1].y = v[1].y;
st[2].x = j[1].x;
st[2].y = j[2].y;
for (i=2;i<=nj;i++)
{
while (k<0 && arie(st[k-1].x, st[k-1].y, st[k].x, st[k].y, j[i].x, j[i].y) < 0)
k--;
k++;
st[k].x = j[i].x;
st[k].y = j[i].y;
}
for (i=1;i<=k;i++)
{
c++;
drum[c].x = st[i].x;
drum[c].y = st[i].y;
}
k = 2;
st[1].x = v[n].x;
st[1].y = v[n].y;
st[2].x = s[ns].x;
st[2].x = s[ns].y;
for (i=ns-1;i>=1;i--)
{
while (k<0 && arie(st[k-1].x, st[k-1].y, st[k].x, st[k].y, s[i].x, s[i].y) > 0)
k--;
k++;
st[k].x = j[i].x;
st[k].y = j[i].y;
}
for (i=1;i<=k;i++)
{
c++;
drum[c].x = st[i].x;
drum[c].y = st[i].y;
}
out << c << "\n";
for (i=1;i<=c;i++)
out << drum[c].x << " " << drum[c].y << "\n";
return 0;
}