Pagini recente » Cod sursa (job #1046112) | Cod sursa (job #2287590) | Cod sursa (job #1745051) | Cod sursa (job #1199231) | Cod sursa (job #2884281)
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream fin ("infasuratoare.in");
ofstream fout ("infasuratoare.out");
struct punct
{
long double x, y;
} p[120001];
long double det (punct a, punct b, punct c)
{
return (b.x-a.x)*(c.y-a.y) - (c.x-a.x)*(b.y-a.y);
}
bool comp (punct a, punct b)
{
return det (p[1], a, b) > 0;
}
int s[120001];
int main()
{
int n, i, ind = 1;
fin >> n;
for (i = 1; i<=n; i++)
{
fin >> p[i].x >> p[i].y;
if (p[i].y < p[ind].y || (p[ind].y == p[i].y && p[i].x < p[ind].x))
ind = i;
}
swap (p[1], p[ind]);
sort (p+2, p+n+1, comp);
s[0] = s[1] = 1;
for (i = 2; i<=n; i++)
{
while (s[0] >= 2 && det (p[s[s[0]-1]], p[s[s[0]]], p[i]) <= 0)
s[0]--;
s[++s[0]] = i;
}
fout << fixed << setprecision (15);
fout << s[0] << '\n';
for (i = 1; i<=s[0]; i++)
fout << p[s[i]].x << ' ' << p[s[i]].y << '\n';
return 0;
}