Pagini recente » Cod sursa (job #2430590) | Cod sursa (job #1529993) | Cod sursa (job #2232667) | Cod sursa (job #744507) | Cod sursa (job #2923406)
#include <iostream>
#include <fstream>
#include <cmath>
#include <vector>
#include <string>
#include <algorithm>
#include <iomanip>
#define x first
#define y second
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
const int N_MAX = 12e4 + 5;
int N;
pair <double, double> v[N_MAX];
int st1[N_MAX], st2[N_MAX];
vector <pair <double, double>> Ans;
bool CheckPop(pair<double, double> A, pair<double, double> B, pair<double, double> C) {
return ((C.y - A.y) * (B.x - A.x) - (B.y - A.y) * (C.x - A.x) <= 0);
}
void ConvexHull(int st[]) {
int idx = 0;
st[++idx] = 1;
st[++idx] = 2;
for (int i = 3; i <= N; i++) {
while (idx > 1 && CheckPop(v[st[idx - 1]], v[st[idx]], v[i])) {
idx--;
}
st[++idx] = i;
}
if (Ans.size() == 0) {
for (int i = 1; i <= idx; i++) {
Ans.push_back(v[st[i]]);
}
}
else {
for (int i = 2; i < idx; i++) {
Ans.push_back(v[st[i]]);
}
}
}
int main() {
ios_base::sync_with_stdio(false);
fin.tie(NULL);
fout.tie(NULL);
fin >> N;
for (int i = 1; i <= N; i++) {
fin >> v[i].x >> v[i].y;
}
sort(v + 1, v + N + 1);
ConvexHull(st1);
reverse(v + 1, v + N + 1);
ConvexHull(st2);
fout << Ans.size() << "\n";
for (int i = 0; i < Ans.size(); i++) {
fout << fixed << setprecision(10) << Ans[i].x << " " << Ans[i].y << "\n";
}
return 0;
}