Pagini recente » Cod sursa (job #1336063) | Cod sursa (job #1640992) | Cod sursa (job #1574277) | Statistici Stanga Catalin (domnulsta) | Cod sursa (job #2756066)
#include <fstream>
#include <algorithm>
#include <cmath>
#include <iomanip>
using namespace std;
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
#define DIM 120005
const double eps = 1.0e-14;
int st[DIM], n, i, vf, sel[DIM], semn;
struct nanu {
double x, y;
} v[DIM], pct;
static inline double det(nanu a, nanu b, nanu c) {
return (b.x - a.x) * (c.y - a.y) - (c.x - a.x) * (b.y - a.y);
}
static inline int ccw(nanu a, nanu b, nanu c){
double k = det(a, b, c); ///comparare a 2 double uri
if(fabs(k) < eps)
return 0;
if(k >= eps)
return 1;
return -1;
}
static inline bool cmp(nanu a, nanu b){
return ccw(pct, a, b) > 0 ;
}
int main() {
cin >> n;
cin >> v[1].x >> v[1].y;
for(i = 2; i <= n; i++){
cin >> v[i].x >> v[i].y;
if(v[i].y - v[1].y <= -eps || (fabs(v[i].y - v[1].y) < eps && v[i].x - v[1].x <= -eps))
swap(v[1], v[i]); ///punctul cu cel mai mic y;
}
pct = v[1];
sort(v + 2, v + n + 1, cmp);
st[++vf] = 1; ///indicele primului punct;
st[++vf] = 2;
sel[2] = 1;
i = 3, semn = 1;
while(!sel[1]) {
while(sel[i] != 0) {
if(i == n)
semn *= -1;
i += semn;
}
while(vf >= 2 && ccw(v[st[vf - 1]], v[st[vf]], v[i]) == -1)
sel[st[vf--]] = 0;
sel[i] = 1;
st[++vf] = i;
}
cout << vf - 1 << '\n';
for(i = 1; i < vf; i++)
cout << fixed << setprecision(6) << v[st[i]].x << " " << v[st[i]].y << '\n';
return 0;
}