Pagini recente » Cod sursa (job #1897082) | Cod sursa (job #7165) | Cod sursa (job #160123) | Cod sursa (job #158441) | Cod sursa (job #2786394)
#include <bits/stdc++.h>
#define arr array <double, 2>
using namespace std;
inline void Open(const string Name) {
#ifndef ONLINE_JUDGE
(void)!freopen((Name + ".in").c_str(), "r", stdin);
(void)!freopen((Name + ".out").c_str(), "w", stdout);
#endif
}
const double EPS = 1e-12;
arr v[120001];
int vis[120001], st[120001];
int N, head;
double cross_prod(arr O, arr A, arr B) {
return (A[0] - O[0]) * (B[1] - O[1]) - (B[0] - O[0]) * (A[1] - O[1]);
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
Open("infasuratoare");
cin >> N;
for(int i = 1;i <= N;i++)
cin >> v[i][0] >> v[i][1];
sort(v + 1, v + N + 1);
vis[2] = st[1] = 1, head = st[2] = 2;
for(int i = 1, p = 1;i > 0;i += (p = (i == N? -p : p))) {
if(vis[i] == 1) continue;
while(head >= 2 && cross_prod(v[st[head - 1]], v[st[head]], v[i]) < EPS)
vis[st[head--]] = 0;
st[++head] = i;
vis[i] = 1;
}
cout << head - 1 << "\n";
cout << setprecision(6) << fixed;
for(int i = 1;i < head;i++)
cout << v[st[i]][0] << " " << v[st[i]][1] << "\n";
return 0;
}