Pagini recente » Cod sursa (job #1956966) | Cod sursa (job #1408085) | Cod sursa (job #821243) | Cod sursa (job #1490332) | Cod sursa (job #1398930)
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>
using namespace std;
struct Point {
double x,y;
};
bool operator<(const Point &a, const Point &b) {
if(a.x == b.x) {
return a.y < b.y;
}
return a.x < b.x;
}
double cross(Point p1, Point p2, Point p3) {
return p1.x*p2.y + p2.x*p3.y + p3.x*p1.y - p1.y*p2.x - p2.y*p3.x - p3.y*p1.x;
}
int main() {
ifstream in("infasuratoare.in");
unsigned n;
in >> n;
vector<Point> points(n);
for(Point &p:points) {
in >> p.x >> p.y;
}
sort(points.begin(), points.end());
vector<Point> top;
for(unsigned i = 0; i < points.size(); ++i) {
while(top.size() >= 2 && cross(*(top.end()-2),*(top.end()-1),points[i]) <= 0) {
top.pop_back();
}
top.push_back(points[i]);
}
top.pop_back();
vector<Point> bottom;
for(int i = points.size()-1; i >= 0; --i) {
while(bottom.size() >= 2 && cross(*(bottom.end()-2),*(bottom.end()-1),points[i]) <= 0) {
bottom.pop_back();
}
bottom.push_back(points[i]);
}
bottom.pop_back();
ofstream out("infasuratoare.out");
out << top.size() + bottom.size() << '\n';
out << setprecision(6) << fixed;
for(Point p:top) {
out << p.x << ' ' << p.y << '\n';
}
for(Point p:bottom) {
out << p.x << ' ' << p.y << '\n';
}
return 0;
}