Pagini recente » Cod sursa (job #2476948) | Cod sursa (job #10879) | Cod sursa (job #840143) | Cod sursa (job #288766) | Cod sursa (job #2142045)
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include <iomanip>
using namespace std;
struct point {
double x, y, rad;
};
bool cmp(const point& a, const point& b) {
return a.rad < b.rad;
}
bool is_convex(point a, point b, point c) {
double det = (a.x - c.x) * (b.y - a.y) + (a.x - b.x) * (a.y - c.y);
return det >= 0;
}
vector<point> convex_hull(vector<point>& A) {
vector<point> H(A.size());
H[0] = A[0];
H[1] = A[1];
int h_size = 2;
for (int i = 2; i < A.size(); i++) {
while (h_size > 1 && !is_convex(H[h_size - 2], H[h_size - 1], A[i])) {
h_size--;
}
H[h_size++] = A[i];
}
H.resize(h_size);
return H;
}
int main() {
freopen("infasuratoare.in", "r", stdin);
freopen("infasuratoare.out", "w", stdout);
int N;
cin>>N;
vector<point> A(N);
int o_i, i;
double o_x, o_y;
for (i = 0; i < N; i++) {
cin >> A[i].x >> A[i].y;
if (i == 0 || A[i].x < o_x || (A[i].x == o_x && A[i].y < o_y)) {
o_i = i; o_x = A[i].x; o_y = A[i].y;
}
}
point aux = A[0];
A[0] = A[o_i];
A[o_i] = aux;
for (i = 1; i < N; i++) {
A[i].rad = atan2(A[i].y - A[0].y, A[i].x - A[0].x);
}
sort(A.begin() + 1, A.end(), cmp);
vector<point> V = convex_hull(A);
cout << V.size() << endl;
cout << fixed;
cout << setprecision(6);
for (i = 0; i < V.size(); i++) {
cout << V[i].x << ' ' << V[i].y << endl;
}
return 0;
}