Pagini recente » Cod sursa (job #1271424) | Istoria paginii planificare/sedinta-20091023 | Istoria paginii utilizator/bielovechocolate | Cod sursa (job #1307490) | Cod sursa (job #2308946)
#include <fstream>
#include <iomanip>
#include <algorithm>
#define mp make_pair
#define pdd pair <double, double>
using namespace std;
const int NMAX = 120005;
struct el
{
double dy, dx, x, y;
el()
{
this->dy = this->dx = this->x = this->y = 0;
}
el(const double &dy, const double &dx, const double &x, const double &y)
{
this->dy = dy;
this->dx = dx;
this->x = x;
this->y = y;
}
inline bool operator<(const el &other) const
{
return this->dy * other.dx < other.dy * this->dx;
}
};
el a[NMAX];
pdd v[NMAX], st[NMAX];
int n, m, top;
inline pdd Slope(const double &x1, const double &y1, const double &x2, const double &y2)
{
double retdy = y2 - y1, retdx = x2 - x1;
if ((retdy < 0 && retdx < 0) || (retdy > 0 && retdx < 0))
retdy = -retdy, retdx = -retdx;
return mp(retdy, retdx);
}
inline bool PositiveDet(pdd a, pdd b, pdd c)
{
return (((a.first * b.second + b.first * c.second + c.first * a.second) - (b.second * c.first + c.second * a.first + a.second * b.first)) > 0);
}
int main()
{
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
fin >> n;
double startx = 1e9 + 1, starty = 1e9 + 1;
int p;
for (int i = 1;i <= n;++i)
{
fin >> v[i].first >> v[i].second;
if (startx > v[i].first)
{
startx = v[i].first;
starty = v[i].second;
p = i;
}
else if (startx == v[i].first && starty > v[i].second)
{
starty = v[i].second;
p = i;
}
}
int cnt = 0;
for (int i = 1;i <= n;++i)
{
if (i != p)
{
pdd aux = Slope(startx, starty, v[i].first, v[i].second);
if (aux.second == 0)
a[n - (++cnt)] = el(aux.first, aux.second, v[i].first, v[i].second);
else
a[++m] = el(aux.first, aux.second, v[i].first, v[i].second);
}
}
m += cnt;
sort(a + 1, a + m + 1);
st[++top] = mp(startx, starty);
st[++top] = mp(a[1].x, a[1].y);
for (int i = 2;i <= m;++i)
{
pdd curr = mp(a[i].x, a[i].y);
while (top > 2 && !PositiveDet(st[top - 1], st[top], curr))
--top;
st[++top] = curr;
}
fout << top << "\n";
fout << setprecision(12) << fixed;
for (int i = 1;i <= top;++i)
fout << st[i].first << " " << st[i].second << "\n";
fin.close();
fout.close();
return 0;
}