Pagini recente » Cod sursa (job #258893) | Cod sursa (job #2654131) | Cod sursa (job #326779) | Cod sursa (job #2970099) | Cod sursa (job #3156338)
#include <bits/stdc++.h>
using namespace std;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
using ld = long double;
int n;
pair<ld,ld> a[120005];
ld signed_area(pair<ld,ld> x, pair<ld,ld> y, pair<ld,ld> z)
{
ld ar = x.first * y.second - x.second * y.first + y.first * z.second - y.second * z.first + z.first * x.second - z.second * x.first;
return ar;
}
bool cmp(pair<ld,ld> A, pair<ld,ld> B)
{
return signed_area(a[1],A,B) < 0;
}
int main()
{
in >> n;
for (int i = 1; i <= n; i++)
in >> a[i].first >> a[i].second;
for (int i = 2; i <= n; i++)
if (a[i] < a[1])
swap(a[1],a[i]);
sort(a + 2,a + n + 1,cmp);
vector<pair<ld,ld>>stk = {a[1],a[2]};
for (int i = 3; i <= n; i++)
{
while (stk.size() >= 2 and signed_area(stk[stk.size() - 2],stk[stk.size() - 1],a[i]) > 0)
stk.pop_back();
stk.push_back(a[i]);
}
out << setprecision(12) << fixed;
out << stk.size() << '\n';
while (!stk.empty())
out << stk.back().first << ' ' << stk.back().second << '\n',stk.pop_back();
return 0;
}