Pagini recente » Cod sursa (job #2544558) | Cod sursa (job #642984) | Cod sursa (job #2401091) | Cod sursa (job #1413249) | Cod sursa (job #3277693)
#include <bits/stdc++.h>
using namespace std;
/// infoarena.ro/problema/infasuratoare
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;
}
};
punct A[120003];
int n, viz[120003];
int st[12003], top;
/// viz[i] = 1, daca i este punct pe infasuratoare
/// ret. 1, daca A[k] se afla in semiplanul + delimitat
/// de punctele A[i] si A[j], sau ret. -1, altfel
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);
/// prima parte:
st[1] = 1; st[2] = 2;
top = 2; viz[1] = viz[2] = 1;
for (i = 3; i <= n; i++)
{
/// scot din stiva ultimul punct, atat timp
/// cat A[i] se afla in semiplanul minus fata
/// de dreapta determinata de ultimele 2 puncte din st
while (top > 1 && F(st[top - 1], st[top], i) < 0)
{
viz[st[top]] = 0;
top--;
}
st[++top] = i;
viz[i] = 1;
}
/// a doua parte:
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;
}