Pagini recente » Cod sursa (job #843538) | Cod sursa (job #3259736) | Cod sursa (job #2155760) | Cod sursa (job #1265108) | Cod sursa (job #3272585)
#include <iostream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#define nl '\n'
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
const int NMAX = 120005;
int n, ind = 1;
struct Point
{
double x, y;
};
Point points[NMAX], st[NMAX];
double det(const Point& A, const Point& B, const Point& C)
{
return (A.x-B.x)*(B.y-C.y)-(A.y-B.y)*(B.x-C.x);
}
bool cmp(const Point& A, const Point& B)
{
return det(points[1], A, B) > 0;
}
int main()
{
fin >> n;
for (int i = 1; i <= n; i++)
{
double x, y;
fin >> x >> y;
points[i] = {x, y};
if ((points[i].x < points[ind].x) || (points[i].x == points[ind].x && points[i].y < points[ind].y))
ind = i;
}
swap(points[1], points[ind]);
sort(points+2, points+1+n, cmp);
st[1] = points[1];
st[2] = points[2];
int m = 2;
for (int i = 3; i <= n; i++)
{
while (m >= 2 && det(st[m-1], st[m], points[i]) < 0)
m--;
st[++m] = points[i];
}
fout << m << nl;
fout << fixed << setprecision(6);
for (int i = 1; i <= m; i++)
fout << st[i].x << ' ' << st[i].y << nl;
return 0;
}