Pagini recente » Cod sursa (job #1407131) | Cod sursa (job #1406115) | Cod sursa (job #1490773) | Cod sursa (job #2254613) | Cod sursa (job #1398837)
#include <fstream>
#include <vector>
#include <algorithm>
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;
}
int cross(Point o, Point a, Point b) {
return (a.x-o.x)*(b.y-o.y) - (a.y-o.y)*(b.x-o.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';
for(Point p:top) {
out << p.x << ' ' << p.y << '\n';
}
for(Point p:bottom) {
out << p.x << ' ' << p.y << '\n';
}
return 0;
}