Pagini recente » Cod sursa (job #11641) | Cod sursa (job #1610193) | Cod sursa (job #2754921) | Cod sursa (job #1250011) | Cod sursa (job #2907475)
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
struct pct
{
double x, y;
} v[120002];
pct low;
double cross(pct a, pct b, pct c)
{
return (b.x - a.x) * (c.y - b.y) - (b.y - a.y) * (c.x - b.x);
}
bool cmp(pct a, pct b)
{
return cross(a, b, low) > 0;
}
int st[120002];
int main()
{
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
int n, i;
cin >> n;
low.y = 1000000003;
for (i = 1; i <= n; i++)
{
cin >> v[i].x >> v[i].y;
if (v[i].y < low.y)
low = v[i];
else if (v[i].y == low.y and v[i].x < low.x)
low = v[i];
}
sort(v + 2, v + n + 1, cmp);
st[1] = 1;
st[2] = 2;
int top = 2;
i = 3;
while (i <= n)
{
if (cross(v[i], v[st[top]], v[st[top - 1]]) < 0)
{
st[++top] = i;
i++;
}
else
top--;
}
cout << top << "\n";
for (i = 1; i <= top; i++)
cout << fixed << setprecision(6) << v[st[i]].x << " " << v[st[i]].y << '\n';
}