Pagini recente » Cod sursa (job #1059944) | Cod sursa (job #2119845) | Cod sursa (job #1196961) | Cod sursa (job #1401359) | Cod sursa (job #2829555)
#include <fstream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <iomanip>
class point {
public:
double x, y;
point operator-=(point to_sub) {
x -= to_sub.x;
y -= to_sub.y;
return *this;
}
point operator-(point to_sub) {
point copy = { x, y };
copy -= to_sub;
return copy;
}
};
#define PREC 1e-12
bool Equal(double nr1, double nr2) {
return std::abs(nr1 - nr2) < PREC;
}
bool CartComp(point pt1, point pt2) {
return (Equal(pt1.x, pt2.x) ? (PREC < pt2.y - pt1.y) : (PREC < pt2.x - pt1.x));
}
bool RadComp(point pt1, point pt2) {
return pt1.x * pt2.y > pt1.y * pt2.x;
}
point vec[120005];
int main() {
std::ifstream fin("infasuratoare.in");
std::ofstream fout("infasuratoare.out");
int nrn;
point first;
std::vector <point> wrap;
fin >> nrn;
for (int index = 0; index < nrn; index++) {
fin >> vec[index].x >> vec[index].y;
}
std::sort(vec, vec + nrn, CartComp);
first = vec[0];
for (int index = 0; index < nrn; index++) {
vec[index].x -= first.x;
vec[index].y -= first.y;
}
std::sort(vec + 1, vec + nrn, RadComp);
wrap.push_back(vec[0]);
for (int index = 1; index < nrn; index++) {
while (wrap.size() > 1 && !RadComp(wrap.back() - wrap[wrap.size() - 2], vec[index] - wrap.back())) {
wrap.pop_back();
}
wrap.push_back(vec[index]);
}
fout << wrap.size() << '\n';
for (const point& now : wrap) {
fout << std::fixed << std::setprecision(6) << now.x + first.x << ' ' << now.y + first.y << '\n';
}
}