Pagini recente » Cod sursa (job #3286602) | Cod sursa (job #235859) | Cod sursa (job #3289616) | Cod sursa (job #3293561) | Cod sursa (job #3293565)
#include <bits/stdc++.h>
#define pr pair<double,double>
#define a first
#define b second
using namespace std;
ifstream in ("infasuratoare.in");
ofstream out ("infasuratoare.out");
pr v[120005], rf;
double x, y;
int n, sz;
double xm = -1e9, ym = -1e9;
int poz;
vector<pr> ans;
pr operator - (pr a, pr b)
{
return {a.a - b.a, a.b - b.b};
}
double unghi (pr a, pr b, pr rf)
{
pr x1 = a - rf;
pr x2 = b - rf;
return x1.a * x2.b - x1.b * x2.a;
}
double lung (pr punct)
{
return punct.a * punct.a + punct.b * punct.b;
}
bool cr (pr a, pr b)
{
double x = unghi (a, b, rf);
if (x == 0)
{
return lung (a - rf) < lung (b - rf);
}
return x < 0;
}
bool cr1 (pr a, pr b)
{
double x = unghi (a, b, rf);
if (x == 0)
{
return lung (a - rf) < lung (b - rf);
}
return x > 0;
}
int main()
{
ios_base::sync_with_stdio (false);
in.tie (0);
out.tie (0);
in >> n;
for (int i = 1; i <= n; ++i)
{
in >> x >> y;
if (x > xm)
xm = x, ym = y, poz = i;
else if (x == xm && y < ym)
ym = y, poz = i;
v[i] = {x, y};
}
rf = v[poz];
sort (v + 1, v + n + 1, cr);
ans.push_back (rf);
sz = 1;
for (int i = 2; i <= n; ++i)
{
while (sz > 1 && unghi (ans[sz - 2], v[i], ans.back()) < 0)
ans.pop_back(), --sz;
ans.push_back (v[i]);
++sz;
}
out << sz << '\n';
rf = {0, 0};
sort (ans.begin(), ans.end(), cr1);
out << fixed << setprecision (12);
for (auto i : ans)
out << i.a << ' ' << i.b << '\n';
}