Pagini recente » Cod sursa (job #2304805) | Cod sursa (job #190763) | Cod sursa (job #359066) | Cod sursa (job #2952653) | Cod sursa (job #2685555)
#include <bits/stdc++.h>
#define sz(x) static_cast<int>((x).size())
#define cd complex<double>
#define x real()
#define y imag()
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
bool fcmp(const cd &a, const cd &b) {
if(a.x != b.x)
return a.x < b.x;
return a.y < b.y;
}
double crossP(const cd &a, const cd &b) {
return (conj(a) * b).y;
}
const double EPS = 1e-12;
int main() {
int N;
fin >> N;
vector<cd> a(N);
for(int i = 0; i < N; ++i) {
double X, Y;
fin >> X >> Y;
a[i] = {X, Y};
}
sort(a.begin(), a.end(), fcmp);
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 && crossP(a[S.back()], a[i]) < EPS) {
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';
}