Pagini recente » Cod sursa (job #541976) | Cod sursa (job #1162082) | Cod sursa (job #2765592) | Cod sursa (job #3139450) | Cod sursa (job #3222239)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
const double EPS = 1e-12;
struct Point
{
long double x, y;
bool operator<(Point A) const
{
if (A.y == y) return x < A.x;
return y < A.y;
}
};
Point a[120003];
int n, st[120003], top, viz[120003];
int sol[120003], k;
double cp(Point O, Point A, Point B) {
return (A.x - O.x) * (B.y - O.y) - (B.x - O.x) * (A.y - O.y);
}
void Citire()
{
fin >> n;
for (int i = 1; i <= n; i++)
fin >> a[i].x >> a[i].y;
}
void convex_hull(){
sort(a + 1, a + n + 1);
top = 1;
st[top] = 1;
viz[1] = 1;
for (int i = 2; i <= n; i++)
{
/// scot din stiva elemente cat timp
/// cp(st[top-1], st[top], a[i]) > 0
while (top > 1 && cp(a[st[top-1]], a[st[top]], a[i]) < EPS)
{
viz[st[top]] = 0;
top--;
}
st[++top] = i;
viz[i] = 1;
}
k = top;
for (int i = 1; i <= top; i++)
sol[i] = st[i];
viz[1] = 0;
top = 1;
st[1] = n;
for (int i = n - 1; i >= 1; i--)
if (viz[i] == 0)
{
/// scot din stiva elemente cat timp
/// cp(st[top-1], st[top], a[i]) > 0
while (top > 1 && cp(a[st[top-1]], a[st[top]], a[i]) <EPS)
{
viz[st[top]] = 0;
top--;
}
st[++top] = i;
viz[i] = 1;
}
for (int i = 2; i <= top; i++)
sol[++k] = st[i];
fout << k-1 << "\n";
for (int i = 1; i < k; i++)
{
fout<<setprecision(12)<<fixed<<
a[sol[i]].x << " " << a[sol[i]].y << "\n";
}
fout.close();
}
int main()
{
int i;
fin >> n;
for (int i = 1; i <= n; i++)
fin >> a[i].x >> a[i].y;
convex_hull();
return 0;
}