Pagini recente » Cod sursa (job #1674258) | Cod sursa (job #1336278) | Cod sursa (job #311076) | Cod sursa (job #1188357) | Cod sursa (job #1815202)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <cmath>
#include <map>
#include <stack>
#define DN 1005
#define LD long double
#define LL long long
#define x first
#define y second
#define EPS 1e-9
using namespace std;
typedef pair<double, double> 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;
}
int main() {
int n;
stack<point> hull;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
// freopen("input.txt", "r", stdin);
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.push(p[0]);
hull.push(p[1]);
for (int i = 2; i < n; ++i) {
point pivot = hull.top();
hull.pop();
point prev = hull.top();
while (!is_trigonometric(prev, pivot, p[i])) {
pivot = prev;
hull.pop();
prev = hull.top();
}
hull.push(pivot);
hull.push(p[i]);
}
fout << hull.size() << '\n';
while (!hull.empty()) {
fout << hull.top().x << " " << hull.top().y << '\n';
hull.pop();
}
return 0;
}