Pagini recente » ..::Hyper Kid Designer Profile::.. | ..::Hyper Kid Designer Profile::.. | Cod sursa (job #3309780) | ..::Hyper Kid Designer Profile::.. | Cod sursa (job #3358002)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
struct punct {
long long x, y;
};
long long orientare(punct a, punct b, punct c) {
return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}
bool cmp(punct a, punct b) {
long long orient = orientare({0, 0}, a, b);
if (orient != 0) return orient > 0;
return (a.x * a.x + a.y * a.y) < (b.x * b.x + b.y * b.y);
}
int main() {
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int n;
fin >> n;
vector<punct> v(n + 1);
for (int i = 1; i <= n; i++) {
fin >> v[i].x >> v[i].y;
}
sort(v.begin() + 1, v.end(), [](punct a, punct b) {
if (a.x != b.x) return a.x < b.x;
return a.y < b.y;
});
vector<punct> st;
for (int i = 1; i <= n; i++) {
while (st.size() >= 2 && orientare(st[st.size() - 2], st.back(), v[i]) <= 0) {
st.pop_back();
}
st.push_back(v[i]);
}
for (int i = n - 1; i >= 1; i--) {
while (st.size() >= 2 && orientare(st[st.size() - 2], st.back(), v[i]) <= 0) {
st.pop_back();
}
st.push_back(v[i]);
}
st.pop_back();
fout << st.size() << '\n';
for (auto p : st) {
fout << fixed;
fout.precision(6);
fout << p.x << ' ' << p.y << '\n';
}
return 0;
}