Pagini recente » Cod sursa (job #3244391) | Cod sursa (job #1541867) | Cod sursa (job #1830183) | Cod sursa (job #1130013) | Cod sursa (job #1159895)
#include <fstream>
#include <vector>
#include <iomanip>
#include <queue>
#include <algorithm>
#include <queue>
using namespace std;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
typedef pair<double, double> pereche;
vector<pereche> v;
#define x first
#define y second
double cross(const pereche &a ,const pereche &b, const pereche &c){
return (b.x - a.x) * (c.y - a.y) - (c.x - a.x) * (b.y - a.y);
}
int cmp(const pereche &a, const pereche &b) {
return cross(*v.begin(), a, b) < 0;
}
vector<pereche> infasuratoare;
int main() {
int n;
in>>n;
double minX=1e10, minI = 1;
for (int i = 1; i <= n; i++) {
pereche p;
in>>p.x>>p.y;
if (minX > p.x) {
minX = p.x;
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() - 2), *(infasuratoare.end() - 1), *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(4)<<i->x<<" "<<i->y<<"\n";
}
return 0;
}