Pagini recente » Cod sursa (job #1649775) | preONI 2007, Runda 3, Clasa a 9-a si gimnaziu | Statistici Sincari Sebastian (sebisincari) | Cod sursa (job #207433) | Cod sursa (job #1160929)
#include <fstream>
#include <vector>
#include <iomanip>
#include <queue>
#include <algorithm>
#include <queue>
using namespace std;
#define MAX 100001
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
struct pereche {
double x,y;
};
pereche v[MAX];
pereche infasuratoare[MAX];
int infasuratoareN = 0;
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;
}
int main() {
int n;
in>>n;
double minX=1e10;
int minI = 1;
for (int i = 1; i <= n; i++) {
in>>v[i].x>>v[i].y;
if (minX > v[i].x) {
minX = v[i].x;
minI = i;
}
}
pereche temp = v[1];
v[1] = v[minI];
v[minI] = temp;
sort(v + 2, v + n + 1, cmp);
infasuratoare[1] = v[1];
infasuratoare[2] = v[2];
infasuratoareN = 2;
for (int i = 3; i <= n; i++) {
while (infasuratoareN >= 2 && cross(infasuratoare[infasuratoareN - 1], infasuratoare[infasuratoareN], v[i]) > 0) {
infasuratoareN--;
}
infasuratoare[++infasuratoareN]= v[i];
}
out<<fixed<<infasuratoareN<<"\n";
for (int i = infasuratoareN; i >= 1; i--)
out<<setprecision(9)<<infasuratoare[i].x<<" "<<infasuratoare[i].y<<"\n";
return 0;
}