Pagini recente » Cod sursa (job #1071276) | Cod sursa (job #2266865) | Cod sursa (job #2697170) | Cod sursa (job #1691723) | Cod sursa (job #2650067)
#include <cstdio>
#include <iostream>
#include <iomanip>
#include <algorithm>
using namespace std;
typedef long double ld;
struct point
{
ld x;
ld y;
};
ld f(point a, point b)
{
return (a.x - b.x) * (a.y + b.y);
}
ld f(point a, point b, point c)
{
return f(a, b) + f(b, c) + f(c, a);
}
int g(point a, point b, point c)
{
ld v = f(a, b, c);
if (v == 0)
{
return 0;
}
if (v > 0)
{
return +1;
}
else
{
return -1;
}
}
point min(point a, point b)
{
if (a.x < b.x)
{
return a;
}
if (b.x < a.x)
{
return b;
}
if (a.y < b.y)
{
return a;
}
else
{
return b;
}
}
const int N = 120000 + 7;
int n;
int top;
point p[N];
point stk[N];
bool operator < (point a, point b)
{
return g(p[1], a, b) > 0;
}
int main()
{
freopen ("infasuratoare.in", "r", stdin);
freopen ("infasuratoare.out", "w", stdout);
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> p[i].x >> p[i].y;
}
for (int i = 2; i <= n; i++)
{
if (p[i] < p[1])
{
swap(p[1], p[i]);
}
}
sort(p + 2, p + n + 1);
p[n + 1] = p[1];
for (int i = 1; i <= n + 1; i++)
{
while (top >= 2 && g(stk[top - 1], stk[top], p[i]) <= 0)
{
top--;
}
stk[++top] = p[i];
}
top--;
cout << top << "\n";
for (int i = 1; i <= top; i++)
{
cout << fixed << setprecision(12) << stk[i].x << " " << stk[i].y << "\n";
}
}