Pagini recente » Cod sursa (job #2589858) | Cod sursa (job #2292527) | Cod sursa (job #120223) | Cod sursa (job #1814877) | Cod sursa (job #2936199)
#include <bits/stdc++.h>
using namespace std;
ifstream in("testament.in");
ofstream out("testament.out");
struct punct {
double x, y;
int ind;
punct(double x, double y, int ind) {
this->x = x;
this->y = y;
this->ind = ind;
}
bool operator<(const punct &other) {
if (x != other.x)
return x < other.x;
return y < other.y;
}
void show() { out << fixed << setprecision(6) << x << ' ' << y << '\n'; }
};
bool eval(const punct &a, const punct &b, const punct &c) {
return (c.y - a.y) * (b.x - a.x) - (c.x - a.x) * (b.y - a.y) <= 0;
}
vector<punct> infasuratoare(vector<punct> puncte) {
sort(puncte.begin(), puncte.end());
vector<punct> res;
for (int i = 0; i < puncte.size(); i++) {
while (res.size() >= 2 &&
eval(res[res.size() - 2], res[res.size() - 1], puncte[i])) {
res.pop_back();
}
res.push_back(puncte[i]);
}
int tmp = res.size() + 1;
for (int i = puncte.size() - 2; i >= 0; i--) {
while (res.size() >= tmp &&
eval(res[res.size() - 2], res[res.size() - 1], puncte[i])) {
res.pop_back();
}
res.push_back(puncte[i]);
}
return res;
}
int main() {
vector<punct> puncte;
int n;
in >> n;
for (int i = 0; i < n; i++) {
double x, y;
in >> x >> y;
puncte.push_back(punct(x, y, 0));
}
vector<punct> res = infasuratoare(puncte);
out << res.size() - 1 << '\n';
for (int i = 1; i < res.size(); i++)
res[i].show();
}