Pagini recente » Cod sursa (job #1047365) | Cod sursa (job #1374516) | Cod sursa (job #96266) | Cod sursa (job #2677106) | Cod sursa (job #1156356)
#include <fstream>
#include <vector>
#include <iomanip>
#include <queue>
#include <algorithm>
#include <queue>
using namespace std;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
struct pereche {double x, y; pereche() {x=y=0;}};
vector<pereche> v;
double cross(pereche &a, pereche &b, pereche &c){
return (b.x - a.x) * (c.y - a.y) - (c.x - a.x) * (b.y - a.y);
}
bool cmp(pereche a, pereche b) {
return cross(*v.begin(), a, b) < 0;
}
vector<pereche> infasuratoare;
int main() {
int n;
in>>n;
double minY=1e10, minI;
for (int i = 1; i <= n; i++) {
pereche p;
in>>p.x>>p.y;
if (minY > p.y) {
minY = p.y;
minI = i;
}
v.push_back(p);
}
iter_swap(v.begin() + minI - 1, v.begin());
sort(v.begin() + 1, v.end(), cmp);
infasuratoare.push_back(*(v.begin()));
infasuratoare.push_back(*(v.begin() + 1));
for (vector<pereche>::iterator i = v.begin() + 2; i != v.end(); i++) {
while (infasuratoare.size() >= 2 && cross(*(infasuratoare.end() - 1), *infasuratoare.end(), *i) > 0) {
infasuratoare.pop_back();
}
infasuratoare.push_back(*i);
}
out<<fixed<<infasuratoare.size()<<"\n";
for (vector<pereche>::reverse_iterator i = infasuratoare.rbegin(); i != infasuratoare.rend(); i++) {
out<<setprecision(5)<<i->x<<" "<<i->y<<"\n";
}
return 0;
}