Pagini recente » Cod sursa (job #2167875) | Cod sursa (job #251502) | Cod sursa (job #1017647) | Cod sursa (job #631050) | Cod sursa (job #2720737)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct Points
{
double x, y;
bool operator < (const Points &other) const
{
if(x == other.x)
return y < other.y;
return x < other.x;
}
};
int st[125000];
vector <Points> p;
bool viz[125000];
double Slopes(Points A, Points B, Points C)
{
return (A.y - C.y) * (B.x - C.x) - (A.x - C.x) * (B.y - C.y);
}
int main()
{
int N;
fin >> N;
for(int i = 1; i <= N; i++)
{
double x, y;
fin >> x >> y;
p.push_back({x, y});
}
sort(p.begin(), p.end());
st[1] = 0;
st[2] = 1;
int top = 2;
viz[1] = true;
int pas = 1, poz = 1;
while(!viz[0])
{
while(viz[poz] == true)
{
if(poz == N - 1)
pas = -1;
poz += pas;
}
while(Slopes(p[poz], p[st[top]], p[st[top - 1]]) > 0 && top >= 2)
viz[st[top]] = false, top --;
st[++top] = poz;
viz[poz] = true;
}
top--;
fout << top << '\n';
for(int i = top; i >= 1; i--)
fout << fixed << setprecision(12) << p[st[i]].x << " " << fixed << setprecision(12) << p[st[i]].y << '\n';
return 0;
}