Pagini recente » Cod sursa (job #1161923) | Cod sursa (job #2321795) | Cod sursa (job #2804521) | Cod sursa (job #2095701) | Cod sursa (job #3226363)
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize ("O1")
#pragma GCC optimize ("O2")
#pragma GCC optimize ("O3")
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target ("avx2")
using namespace std;
using namespace __gnu_pbds;
#define ordered_set tree <long long, null_type, less<long long>, rb_tree_tag, tree_order_statistics_node_update>
#define lsb(x)(x & (-x))
const int max_size = 12e4 + 20;
pair <double, double> v[max_size];
vector <int> sus, jos;
double arie (pair <double, double> x, pair <double, double> y, pair <double, double> z)
{
return x.first * (y.second - z.second) + y.first * (z.second - x.second) + z.first * (x.second - y.second);
}
void solve ()
{
int n;
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> v[i].first >> v[i].second;
}
sort(v + 1, v + n + 1);
for (int i = 1; i <= n; i++)
{
while (sus.size() > 1 && arie(v[sus[sus.size() - 2]], v[sus.back()], v[i]) >= 0)
{
sus.pop_back();
}
while (jos.size() > 1 && arie(v[jos[jos.size() - 2]], v[jos.back()], v[i]) <= 0)
{
jos.pop_back();
}
sus.push_back(i);
jos.push_back(i);
}
vector <pair <double, double>> ans;
for (auto f : jos)
{
ans.push_back(v[f]);
}
sus.pop_back();
reverse(sus.begin(), sus.end());
sus.pop_back();
for (auto f : sus)
{
ans.push_back(v[f]);
}
cout << ans.size() << '\n';
for (auto f : ans)
{
cout << fixed << setprecision(6) << f.first << " " << f.second << '\n';
}
cout << '\n';
}
signed main ()
{
#ifdef LOCAL
freopen("test.in", "r", stdin);
freopen("test.out", "w", stdout);
#else
freopen("infasuratoare.in", "r", stdin);
freopen("infasuratoare.out", "w", stdout);
#endif // LOCAL
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
long long tt;
//cin >> tt;
tt = 1;
while (tt--)
{
solve();
}
return 0;
}