Pagini recente » Cod sursa (job #1989551) | Cod sursa (job #1315370) | Cod sursa (job #2988800) | Cod sursa (job #2836511) | Cod sursa (job #3142061)
//#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>
#include <unordered_map>
#include <map>
#include <set>
#include <unordered_set>
#include <bitset>
#include <cstring>
#include <assert.h>
#include <iomanip>
using namespace std;
const string file = "infasuratoare";
ifstream cin(file + ".in");
ofstream cout(file + ".out");
#define FAST ios_base::sync_with_stdio(0), cin.tie(0),cout.tie(0) ;
typedef pair<long double, long double> point;
const int NMAX = 120005;
point v[NMAX];
int n;
long double unghi(point a, point b, point c) {
return (b.first - a.first) * (c.second - a.second) - (b.second - a.second) * (c.first - a.first);
}
bool comp(point c, point b) {
return unghi(v[1], b, c) < 0;
}
vector <point> st;
int main(void)
{
cin >> n;
for (int i = 1; i <= n; ++i) cin >> v[i].first >> v[i].second;
int pos = 1;
for (int i = 1; i <= n; ++i) if (v[pos] > v[i]) pos = i;
swap(v[1], v[pos]);
sort(v + 2, v + n + 1,comp);
st.push_back(v[1]), st.push_back(v[2]);
for (int i = 3; i <= n; ++i) {
while (st.size() >= 2 && unghi(st[st.size() - 1], st[st.size() - 2],v[i]) > 0) st.pop_back();
st.push_back(v[i]);
}
cout << st.size() << '\n';
reverse(st.begin(), st.end());
for (auto it : st) cout << fixed << setprecision(10) << it.first << " " << it.second << '\n';
return 0;
}