Pagini recente » Cod sursa (job #2598685) | Cod sursa (job #1015298) | Cod sursa (job #1348389) | Cod sursa (job #313398) | Cod sursa (job #3286224)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct punct
{
long double x, y;
bool operator<(const punct B) const
{
if (y == B.y) return x < B.x;
return y < B.y;
}
} A[120003];
int n, viz[120003];
int st[120003], top;
int F(int i, int j, int k)
{
long double a, b, c;
a = A[i].y - A[j].y;
b = A[j].x - A[i].x;
c = A[i].x * A[j].y - A[j].x * A[i].y;
if (a * A[k].x + b * A[k].y + c < 0) return -1;
return 1;
}
int main()
{
int i;
fin >> n;
for (i = 1; i <= n; i++)
fin >> A[i].x >> A[i].y;
sort(A + 1, A + n + 1);
st[1] = 1;
st[2] = 2;
top = 2; viz[1] = viz[2] = 1;
for (i = 3; i <= n; i++)
{
while (top > 1 && F(st[top - 1], st[top], i) < 0)
{
viz[st[top]] = 0;
top--;
}
st[++top] = i;
viz[i] = 1;
}
viz[1] = 0;
for (i = n; i >= 1; i--)
if (viz[i] == 0)
{
while (top > 1 && F(st[top - 1], st[top], i) < 0)
{
viz[st[top]] = 0;
top--;
}
st[++top] = i;
viz[i] = 1;
}
fout << (top - 1) << "\n";
for (i = 1; i < top; i++)
fout << setprecision(12) << fixed << A[st[i]].x << " " << A[st[i]].y << "\n";
return 0;
}
//0, 1, 3-5, 7-18, 21, 22, 24-27, 29, 30, 34-36, 42, 44, 45, 47, 48, 51, 54, 56-58