Pagini recente » Cod sursa (job #1661070) | Cod sursa (job #2803505) | Cod sursa (job #359287) | Cod sursa (job #944863) | Cod sursa (job #2400659)
#include <iomanip>
#include <fstream>
#include <algorithm>
#define pdd pair <double, double>
#define mp make_pair
using namespace std;
const int NMAX = 120005;
class point
{
public:
pdd coord, slope;
point()
{
coord = slope = mp(0.0, 0.0);
}
point(pdd a, pdd b)
{
coord = a;
slope = b;
}
inline bool operator<(const point &other) const
{
return this->slope.first * other.slope.second < this->slope.second * other.slope.first;
}
};
int n;
pdd points[NMAX], st[NMAX];
point a[NMAX];
pdd GetSlope(pdd a, pdd b)
{
pdd slope = mp((b.second - a.second), (b.first - a.first));
if ((slope.second < 0 && slope.first < 0) || (slope.second < 0 && slope.first > 0))
{
slope.first *= -1;
slope.second *= -1;
}
return slope;
}
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;
pdd start = mp(1e9 + 5, 1e9 + 5);
int startPos;
for (int i = 1;i <= n;++i)
{
fin >> points[i].first >> points[i].second;
if (points[i].first < start.first)
{
start = points[i];
startPos = i;
}
else if (points[i].first == start.first && points[i].second < start.second)
{
start = points[i];
startPos = i;
}
}
int m = 0;
for (int i = 1;i <= n;++i)
{
if (i == startPos)
continue;
a[++m] = point(points[i], GetSlope(start, points[i]));
}
sort(a + 1, a + m + 1);
int top = 0;
st[++top] = start;
st[++top] = a[1].coord;
for (int i = 2;i <= m;++i)
{
while (top > 2 && !PositiveDet(st[top - 1], st[top], a[i].coord))
--top;
st[++top] = a[i].coord;
}
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;
}