Pagini recente » Cod sursa (job #2867616) | Cod sursa (job #608887) | Cod sursa (job #1691125) | Cod sursa (job #2551089) | Cod sursa (job #3197601)
#include <iostream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#define NMAX 120003
using namespace std;
ifstream fin ("infasuratoare.in");
ofstream fout ("infasuratoare.out");
struct punct {
double x, y;
};
punct points[NMAX], leftPoint, st[NMAX];
int n, leftPointIndex, dr;
int det(punct a, punct b, punct c)
{
return (a.x*b.y + b.x*c.y + a.y*c.x - b.y*c.x - a.y*b.x - c.y*a.x);
}
bool cmp(punct a, punct b)
{
return det(leftPoint, a, b) >= 0;
}
int main()
{
fin >> n;
for (int i = 0; i < n; i++)
{
fin >> points[i].x >> points[i].y;
if (points[i].x < points[leftPointIndex].x || (points[i].x == points[leftPointIndex].x && points[i].y < points[leftPointIndex].y))
leftPointIndex = i;
}
swap(points[leftPointIndex], points[0]); // fixez punctul initial pe 0
leftPoint = points[0];
sort(points + 1, points + n, cmp);
points[n] = points[0];
st[++dr] = leftPoint; // == points[0]
for (int i = 1; i <= n; i++)
{
while (det(st[dr-1], st[dr], points[i]) < 0)
dr--;
st[++dr] = points[i];
}
fout << dr << "\n";
for (int i = 1; i <= dr; i++)
fout << fixed << setprecision(12) << st[i].x << " " << st[i].y << "\n";
return 0;
}