Pagini recente » Cod sursa (job #21915) | Cod sursa (job #101575) | Cod sursa (job #3164677) | Cod sursa (job #1938801) | Cod sursa (job #1159902)
#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[0], 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);
int K=1;
infasuratoare.push_back(v[0]);
infasuratoare.push_back(v[1]);
for (int i =0; i < n; ++i) {
while (K>= 1 && cross(infasuratoare[K-1],infasuratoare[K], v[i]) > 0) --K;
infasuratoare[++K]=v[i];
}
out<<fixed<<infasuratoare.size()<<"\n";
for (vector<pereche>::reverse_iterator i = infasuratoare.rbegin(); i != infasuratoare.rend(); i++) {
out<<setprecision(9)<<i->x<<" "<<i->y<<"\n";
}
return 0;
}