Pagini recente » Cod sursa (job #2148573) | Cod sursa (job #1679060) | Cod sursa (job #970500) | Cod sursa (job #3122247) | Cod sursa (job #1375140)
#include <algorithm>
#include <iostream>
#include <fstream>
#include <vector>
#include <iomanip>
struct vec2 {
double x, y;
vec2(double _x = 0.0, double _y = 0.0) {
x = _x;
y = _y;
}
bool operator>(const vec2& v) const {
if (x == v.x) {
return y > v.y;
}
return x > v.x;
}
vec2 operator-(const vec2& v) const {
return vec2(x - v.x, y - v.y);
}
bool operator==(const vec2& v) const {
return (x == v.x && y == v.y);
}
};
const int MAXN = 120005;
std::ifstream f("infasuratoare.in");
std::ofstream g("infasuratoare.out");
vec2 p[MAXN]; int n; vec2 ref;
std::vector<vec2> sol;
inline bool cmp(const vec2& a, const vec2& b)
{
if (a == ref) {
return true;
}
if (b == ref) {
return false;
}
vec2 p1 = a - ref;
vec2 p2 = b - ref;
return p1.x * p2.y < p2.x * p1.y;
}
bool det(vec2& a, vec2& b, vec2& c)
{
return a.x * b.y + b.x * c.y + c.x * a.y - a.x * c.y - b.x * a.y - c.x * b.y > 0;
}
int main()
{
f >> n;
for (int i = 1; i <= n; i++) {
f >> p[i].x >> p[i].y;
if (ref > p[i]) {
ref = p[i];
}
}
std::sort(p + 1, p + n + 1, cmp);
for (int i = 1; i <= n; i++) {
while (sol.size() > 1 && det(sol[sol.size() - 2], sol.back(), p[i])) {
sol.pop_back();
}
sol.push_back(p[i]);
}
reverse(sol.begin(), sol.end());
g << sol.size() << '\n';
for (int i = 0; i < sol.size(); i++) {
g << std::fixed << std::setprecision(6) << sol[i].x << ' ' << sol[i].y << '\n';
}
//system("pause");
f.close();
g.close();
return 0;
}