Pagini recente » Cod sursa (job #1570376) | Cod sursa (job #175744) | Cod sursa (job #485069) | Cod sursa (job #2990470) | Cod sursa (job #1815745)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <cmath>
#include <map>
#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<double, double> point;
point p[DN];
map<point, double> angle;
bool cmp(point a, point b) {
return angle[a] > angle[b];
}
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]);
}
for (int i = 1; i < n; ++i)
angle[p[i]] = atan2(p[i].y - p[0].y, p[i].x - p[0].x);
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;
}