Pagini recente » Cod sursa (job #1478714) | Cod sursa (job #84931) | Cod sursa (job #2794312) | Cod sursa (job #2076825) | Cod sursa (job #1815528)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <cmath>
#include <map>
#include <stack>
#define DN 120005
#define LD long double
#define LL long long
#define x first
#define y second
#define EPS 1e-9
using namespace std;
typedef pair<LD, LD> point;
point p[DN];
bool cmp(point a, point b) {
return atan2(a.y - p[0].y, a.x - p[0].x) > atan2(b.y - p[0].y, b.x - p[0].x);
}
bool is_trigonometric(point a, point c, point b) {
return (a.x - c.x) * (b.y - c.y) - (b.x - c.x) * (a.y - c.y) > 0;
}
point hull[DN];
int m;
int main() {
int n;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
// freopen("input.txt", "r", stdin);
// ifstream fin("input.txt");
fin >> n;
for (int i = 0; i < n; ++i) {
fin >> p[i].x >> p[i].y;
}
for (int i = 1; i < n; ++i) {
if (p[i].x < p[0].x || (p[i].x == p[0].x && p[i].y < p[0].y))
swap(p[0], p[i]);
}
sort(p+1, p+n, cmp);
hull[m++] = p[0];
hull[m++] = p[1];
for (int i = 2; i < n; ++i) {
point pivot = hull[--m];
point prev = hull[m-1];
while (!is_trigonometric(prev, pivot, p[i])) {
pivot = prev;
--m;
prev = hull[m - 1];
}
hull[m++] = pivot;
hull[m++] = p[i];
}
fout << m << '\n';
while (m) {
--m;
fout << fixed << setprecision(12) << hull[m].x << " " << hull[m].y << '\n';
}
return 0;
}