Pagini recente » Cod sursa (job #1854913) | Cod sursa (job #116636) | Cod sursa (job #1737357) | Cod sursa (job #442568) | Cod sursa (job #2976906)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct Punct
{
long double x, y;
bool operator<(Punct A) const
{
if (A.y == y) return x < A.x;
return y < A.y;
}
};
Punct a[120003];
int n, st[120003], top, viz[120003];
int sol[120003], k;
long double F(Punct A, Punct B, Punct C)
{
long double a, b, c;
a = B.y - A.y;
b = A.x - B.x;
c = A.x*(A.y - B.y) + A.y * (B.x - A.x);
return a * C.x + b * C.y + c;
}
void Citire()
{
fin >> n;
for (int i = 1; i <= n; i++)
fin >> a[i].x >> a[i].y;
}
int main()
{
int i;
Citire();
sort(a + 1, a + n + 1);
top = 1;
st[top] = 1;
viz[1] = 1;
for (i = 2; i <= n; i++)
{
/// scot din stiva elemente cat timp
/// F(st[top-1], st[top], a[i]) > 0
while (top > 1 && F(a[st[top-1]], a[st[top]], a[i]) > 0)
{
viz[st[top]] = 0;
top--;
}
st[++top] = i;
viz[i] = 1;
}
k = top;
for (i = 1; i <= top; i++)
sol[i] = st[i];
viz[1] = 0;
top = 1;
st[1] = n;
for (i = n - 1; i >= 1; i--)
if (viz[i] == 0)
{
/// scot din stiva elemente cat timp
/// F(st[top-1], st[top], a[i]) > 0
while (top > 1 && F(a[st[top-1]], a[st[top]], a[i]) > 0)
{
viz[st[top]] = 0;
top--;
}
st[++top] = i;
viz[i] = 1;
}
for (i = 2; i <= top; i++)
sol[++k] = st[i];
fout << k-1 << "\n";
for (i = 1; i < k; i++)
{
fout<<setprecision(12)<<fixed<<
a[sol[i]].x << " " << a[sol[i]].y << "\n";
}
fout.close();
return 0;
}