# Cod sursa(job #2142045)

Utilizator Data 24 februarie 2018 18:15:41 Infasuratoare convexa 100 cpp done Arhiva educationala 1.51 kb
``````#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include <iomanip>
using namespace std;

struct point {
};

bool cmp(const point& a, const point& b) {
}

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;
}
``````