Pagini recente » Cod sursa (job #145119) | Cod sursa (job #316207) | Cod sursa (job #3196379) | Cod sursa (job #2272957) | Cod sursa (job #2062650)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
#define ld long double
#define pld pair<ld, ld>
#define x first
#define y second
#define pii pair<int,int>
const int Nmax = 120000 + 5;
pld p[Nmax], ans[Nmax];
stack<pii>S;
int m, n;
ld det = 0;
pld a, b, c;
bool cmp(pld p1, pld p2)
{
if(p1.y == p2.y)
return p1.x < p2.x;
return p1.y < p2.y;
}
void inf(bool vr)
{
S.push({2, 1});
for(int i = 3; i <= n; ++i)
{
if(S.empty())
{
S.push({1, i});
continue;
}
a = p[S.top().x];
b = p[S.top().y];
c = p[i];
det = (b.x - a.x)*(c.y - a.y) - (b.y - a.y)*(c.x - a.x);
if((!vr && det >= 0) || (vr && det < 0))
S.push({S.top().y, i});
else S.pop(), i--;
}
}
int main()
{
fin >> n;
for(int i = 1; i <= n; ++i)
fin >> p[i].x >> p[i].y;
sort(p + 1, p + n + 1, cmp);
inf(0);
ans[1].x = p[1].x;
ans[1].y = p[1].y;
while(!S.empty())
{
ans[S.size() + 1].x = p[S.top().y].x;
ans[S.size() + 1].y = p[S.top().y].y;
++m;
}
inf(1);
while(!S.empty())
{
++m;
ans[m].x = p[S.top().y].x;
ans[m].y = p[S.top().y].y;
}
--m;
for(int i =1; i <= m; ++i)
fout << p[i].x << " " << p[i].y << '\n';
return 0;
}