Pagini recente » Cod sursa (job #3292991) | Cod sursa (job #3291454) | clasament-arhiva-educationala | Cod sursa (job #3286762) | Cod sursa (job #3293184)
#include <bits/stdc++.h>
using namespace std;
ifstream in ("infasuratoare.in");
ofstream out ("infasuratoare.out");
struct pr
{
double a, b;
bool operator< (const pr &x) const
{
return (make_pair (a, b) < make_pair (x.a, x.b));
}
};
pr v[120005], rf;
double x, y;
int n, sz, 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 pct)
{
return pct.a * pct.a + pct.b * pct.b;
}
bool cr (pr a, pr b)
{
double ung = unghi (a, b, rf);
if (ung == 0)
{
return lung (a - rf) < lung (b - rf);
}
return ung > 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;
v[i] = {x, y};
}
sort (v + 1, v + n + 1);
for (int i = 1; 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;
}
ans.pop_back();
--sz;
reverse (v + 1, v + n + 1);
for (int i = 1; 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;
}
ans.pop_back();
--sz;
out << sz << '\n';
rf = {0, 0};
sort (ans.begin(), ans.end(), cr);
out << fixed << setprecision (12);
for (auto i : ans)
out << i.a << ' ' << i.b << '\n';
}