Pagini recente » Cod sursa (job #542214) | Cod sursa (job #1773751) | Cod sursa (job #168445) | Cod sursa (job #244840) | Cod sursa (job #2736974)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int N;
struct Point
{
long double x, y;
bool operator < (const Point &other) const
{
return x < other.x;
}
};
Point v[125000];
bool taken[125000];
int st[125000], vf;
long double Slope(Point A, Point B, Point C)
{
return (C.y - A.y) * (B.x - A.x) - (C.x - A.x) * (B.y - A.y);
}
void solve()
{
st[1] = 1;
st[2] = 2;
vf = 2;
int pas = 1, crt = 2;
taken[2] = true;
while(taken[1] == false)
{
while(taken[crt] == true)
{
if(crt == N)
pas = -1;
crt += pas;
}
while(vf >= 2 && Slope(v[crt], v[st[vf]], v[st[vf - 1]]) > 0)
taken[st[vf]] = false, vf--;
taken[crt] = true;
st[++vf] = crt;
}
}
int main()
{
fin >> N;
for(int i = 1; i <= N; i++)
{
long double x, y;
fin >> x >> y;
v[i] = {x, y};
}
sort(v + 1, v + N + 1);
solve();
fout << vf - 1 << '\n';
for(int i = 2; i <= vf; i++)
fout << fixed << setprecision(12) << v[st[i]].x << " " << fixed << setprecision(12) << v[st[i]].y << '\n';
return 0;
}