Pagini recente » Cod sursa (job #2330915) | Cod sursa (job #908799) | Cod sursa (job #1437688) | Cod sursa (job #2402184) | Cod sursa (job #1414904)
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define fs first
#define sc second
#define pob pop_back
#define pub push_back
#define eps 1E-7
#define sz(a) a.size()
#define count_one __builtin_popcount;
#define count_onell __builtin_popcountll;
#define fastIO ios_base::sync_with_stdio(false)
#define PI (acos(-1.0))
#define linf (1LL<<62)//>4e18
#define inf (0x7f7f7f7f)//>2e9
#ifndef ONLINE_JUDGE
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
#endif
const int MAXN = 120010;
int n, head;
pair<double, double> v[MAXN];
pair<double, double> res[MAXN];
inline double pantaComp(const pair<double, double> &A, const pair<double, double> &B, const pair<double, double> &C) {
return (B.fs - A.fs) * (C.sc - A.sc) - (C.fs - A.fs) * (B.sc - A.sc);
}
inline int comp (const pair<double, double> &A, const pair<double, double> &B) {
return pantaComp(v[1], A, B) < 0;
}
void read() {
fin >> n;
int x, y;
int minpos = 1;
for(int i = 1; i <= n; ++i) {
fin >> v[i].fs >> v[i].sc;
if(v[i].fs < v[minpos].fs)
minpos = i;
}
swap(v[minpos], v[1]);
}
int main() {
read();
sort(v + 2, v + n + 1, comp);
res[1] = v[1];
res[2] = v[2];
head = 2;
for(int i = 3; i <= n; ++i) {
while(head >= 2 && pantaComp(res[head - 1], res[head], v[i]) > 0)
--head;
res[++head] = v[i];
}
fout << head << "\n";
for(int i = head; i; --i) {
fout << fixed << setprecision(9) << res[i].fs << " " << res[i].sc << "\n";
}
return 0;
}