Pagini recente » Cod sursa (job #1025090) | Cod sursa (job #1531966) | Cod sursa (job #605990) | Cod sursa (job #1834245) | Cod sursa (job #2685559)
#include <bits/stdc++.h>
#define sz(x) static_cast<int>((x).size())
#define pd pair<double,double>
#define x first
#define y second
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
const double EPS = 1e-12;
bool check(pd O, pd A, pd B) {
return ((A.x - O.x) * (B.y - O.y) - (B.x - O.x) * (A.y - O.y)) < EPS;
}
int main() {
int N;
fin >> N;
vector<pd> a(N);
for(pd &x : a)
fin >> x.x >> x.y;
sort(a.begin(), a.end());
vector<int> S;
S.emplace_back(0), S.emplace_back(1);
vector<bool> viz(N);
viz[1] = true;
for(int i = 0, add = 1; i >= 0; i += (add = (i == N - 1 ? -add : add))) {
if(viz[i])
continue;
while(sz(S) > 1 && check(a[sz(S) - 2], a[S.back()], a[i])) {
viz[S.back()] = false;
S.pop_back();
}
S.emplace_back(i);
viz[i] = true;
}
fout << sz(S) - 1 << '\n' << fixed << setprecision(12);
for(int i = 0; i < sz(S) - 1; ++i)
fout << a[S[i]].x << ' ' << a[S[i]].y << '\n';
}