Pagini recente » Borderou de evaluare (job #2745294) | Cod sursa (job #1534717) | Heap-uri | Diferente pentru dinic intre reviziile 8 si 9 | Cod sursa (job #2443406)
#define DM 120001
#include <algorithm>
#include <fstream>
#include <iomanip>
#include <math.h>
#include <vector>
using namespace std;
ifstream fi ("infasuratoare.in");
ofstream fo ("infasuratoare.out");
double a, b, det;
int n, h;
class Point {
public:
double x, y, pos;
void calc_Pos() {
pos = atan2(y, x);
};
bool operator < (Point &other) const {
if (pos == other.pos)
return x > other.x || y > other.y;
if (pos >= 0 && other.pos >= 0)
return pos < other.pos;
if (pos >= 0 && other.pos < 0)
return true;
if (pos < 0 && other.pos >= 0)
return false;
return pos < other.pos;
};
bool operator == (Point &other) const {
return (x == other.x && y == other.y && pos == other.pos);
};
};
vector <Point> v, sol;
int main() {
fi >> n;
for (int i = 0; i < n; ++i) {
fi >> a >> b;
v.push_back({a, b});
v[i].calc_Pos();
}
sort(v.begin(), v.end());
for (auto i:v) {
if (i == *v.begin()) {
sol.push_back(i);
continue;
}
if (sol.size() > 1) {
det = sol[sol.size()-2].x*sol[sol.size()-1].y +
sol[sol.size()-1].x*i.y +
i.x*sol[sol.size()-2].y -
sol[sol.size()-1].y*i.x -
i.y*sol[sol.size()-2].x -
sol[sol.size()-2].y*sol[sol.size()-1].x;
while (sol.size() > 1 && det < 0) {
sol.pop_back();
det = sol[sol.size()-2].x*sol[sol.size()-1].y +
sol[sol.size()-1].x*i.y +
i.x*sol[sol.size()-2].y -
sol[sol.size()-1].y*i.x -
i.y*sol[sol.size()-2].x -
sol[sol.size()-2].y*sol[sol.size()-1].x;
}
}
sol.push_back(i);
}
fo << sol.size() << '\n';
for (auto i:sol)
fo << fixed << setprecision(12) << i.x << ' ' << i.y << '\n';
return 0;
}