Pagini recente » Cod sursa (job #3191042) | Cod sursa (job #1639834) | Cod sursa (job #3005381) | Cod sursa (job #2829060) | Cod sursa (job #3244557)
#include <bits/stdc++.h>
#define int long long
#define sz(a) int((a).size())
#define all(a) (a).begin(), (a).end()
#define lsb(x) (x & (-x))
#define vi vector<int>
#define YES { cout << "YES" << endl; return; }
#define NO { cout << "NO" << endl; return; }
using ll = long long;
using pii = std::pair<int, int>;
using pdd = std::pair<double, double>;
using namespace std;
ifstream fin ("infasuratoare.in");
ofstream fout ("infasuratoare.out");
double arie(pdd a, pdd b, pdd c){
return a.first*b.second + b.first*c.second + c.first*a.second -b.second*c.first -c.second*a.first - a.second*b.first;
}
ofstream&operator << (ofstream&iesire, pdd&a){
iesire << a.first << " " << a.second << '\n';
return iesire;
}
bool cmp(pdd a, pdd b){
if (a.first != b.first)
return a.first < b.first;
}
void solve_testcase() {
int n;
fin >> n;
vector<pdd>p(n);
vi tip(n, 0);
for (auto &it : p)
fin >> it.first >> it.second;
sort(all(p));
for (int i = 1; i < n - 1; ++i){
if (arie(p[0], p.back(), p[i]) < 0)
tip[i] = 1;
if (arie(p.front(), p.back(), p[i]) > 0)
tip[i] = 2;
}
vector<pdd> stk = {p.front()};
for (int i = 1; i < n; ++i){
if (tip[i] != 2){
while (stk.size() > 1 && arie(stk[stk.size()], stk[stk.size() - 1], p[i]) < 0)
stk.pop_back();
stk.push_back(p[i]);
}
}
int csz = stk.size();
for (int i = n - 2; i >= 0; --i){
if (tip[i] != 1){
while (stk.size() > csz && arie(stk[stk.size()], stk[stk.size() - 1], p[i]) < 0)
stk.pop_back();
stk.push_back(p[i]);
}
}
stk.pop_back();
fout << stk.size() << '\n';
fout << fixed << setprecision(6);
for (auto &it : stk)
fout << it;
}
signed main() {
int t = 1;
// cin >> t;
while (t--)
solve_testcase();
return 0;
}