Pagini recente » Cod sursa (job #1966906) | Cod sursa (job #372455) | Cod sursa (job #550543) | Cod sursa (job #851766) | Cod sursa (job #1780108)
#include <bits/stdc++.h>
using namespace std;
typedef double f64;
const int SPQR = 120005;
const f64 EPS = 1e-16;
struct PTX {
f64 x, y;
void rot(double alpha) {
f64 _x = x * cos(alpha) - y * sin(alpha);
f64 _y = x * sin(alpha) + y * cos(alpha);
x = _x;
y = _y;
}
bool operator < (const PTX &arg) const {
return (abs(x-arg.x)<EPS) ? (y < arg.y) : (x < arg.x);
}
};
PTX pts[SPQR];
bool gws[SPQR];
vector<pair<PTX, PTX> > vag[SPQR];
f64 ccw(const PTX &a, const PTX &b, const PTX &c) {
return (a.x-b.x)*(c.y-b.y)-(a.y-b.y)*(c.x-b.x);
}
vector<PTX> make_hull(vector<PTX> ptr) {
vector<PTX> hull, ue, le;
sort(ptr.begin(), ptr.end());
for(int i=0; i<ptr.size(); ++i) {
while(ue.size()>=2 && ccw(ue[ue.size()-2], ue[ue.size()-1], ptr[i])>EPS)
ue.pop_back();
while(le.size()>=2 && ccw(le[le.size()-2], le[le.size()-1], ptr[i])<-EPS)
le.pop_back();
ue.push_back(ptr[i]);
le.push_back(ptr[i]);
}
for(int i=0; i<ue.size(); ++i)
hull.push_back(ue[i]);
for(int i=le.size()-2; i>0; --i)
hull.push_back(le[i]);
return hull;
}
int main(void) {
ifstream fi("infasuratoare.in");
ofstream fo("infasuratoare.out");
int n;
vector<PTX> pts, hull;
fi >> n;
pts.resize(n);
for(int i=0; i<n; ++i) {
fi >> pts[i].x >> pts[i].y;
// pts[i].rot(acos(-1) / 7);
}
hull = make_hull(pts);
fo << setprecision(6) << fixed;
for(auto i: hull)
fo << i.x << ' ' << i.y << '\n';
return 0;
}