Pagini recente » Cod sursa (job #1919346) | Cod sursa (job #93136) | Cod sursa (job #24472) | Cod sursa (job #404168) | Cod sursa (job #1817884)
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxN = 120000;
class Point {
public:
double x, y, panta;
Point(double _x = 0, double _y = 0) : x(_x), y(_y) {
panta = y / x;
}
inline bool operator < (const Point& other) const;
pair<double, double> pereche() const {
return make_pair(x, y);
}
} v[maxN + 1], st[maxN + 1];;
inline double crossProduct(const Point& A, const Point& B, const Point& C) {
return (B.x - A.x) * (C.y - A.y) - (B.y - A.y) * (C.x - A.x);
}
inline bool Point::operator < (const Point& other) const {
return crossProduct(v[1], *this, other) < 0;
}
void sortV(int N) {
int pos = 1;
for(int i = 2; i <= N; ++ i)
if(v[i].pereche() < v[pos].pereche())
pos = i;
swap(v[1], v[pos]);
sort(v + 2, v + N + 1);
}
int top;
int main() {
freopen("infasuratoare.in", "r", stdin);
freopen("infasuratoare.out", "w", stdout);
int N;
scanf("%d", &N);
for(int i = 1; i <= N; ++ i)
scanf("%lf %lf", &v[i].x, &v[i].y);
sortV(N);
st[++ top] = v[1];
st[++ top] = v[2];
for(int i = 3; i <= N; ++ i) {
while(top >= 2 and crossProduct(st[top - 1], st[top], v[i]) > 0.0)
-- top;
st[++ top] = v[i];
}
printf("%d\n", top);
for(int i = top; i; -- i)
printf("%.9f %.9f\n", st[i].x, st[i].y);
return 0;
}