Pagini recente » Cod sursa (job #1653119) | Cod sursa (job #1696925) | Clasament 5_martie_simulare_oji_2024_clasele_11_12 | Cod sursa (job #893092) | Cod sursa (job #1247415)
#include <cstdio>
#include <algorithm>
#include <vector>
#define pb push_back
using namespace std;
struct pt {
double x, y;
};
int n;
const double eps = 1e-6;
bool comp(pt a, pt b) {
return ((a.x + eps < b.x) || (a.x == b.x && a.y + eps < b.y));
}
bool cw(pt a, pt b, pt c) {
return a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y) < 0;
}
bool ccw(pt a, pt b, pt c) {
return a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y) > 0;
}
void convex_hull(vector <pt> &a) {
if (a.size() == 1) return ;
sort(a.begin(), a.end(), comp);
pt p1 = a[0], p2 = a.back();
vector <pt> up, down;
up.pb(p1);
down.pb(p1);
for (size_t i = 1; i < a.size(); i++) {
if (i == a.size() - 1 || cw(p1, a[i], p2)) {
while (up.size() >= 2 && !cw(up[up.size() - 2], up[up.size() - 1], a[i]))
up.pop_back();
up.pb(a[i]);
}
if (i == a.size() - 1 || ccw(p1, a[i], p2)) {
while (down.size() >= 2 && !ccw(down[down.size() - 2], down[down.size() - 1], a[i]))
down.pop_back();
down.pb(a[i]);
}
}
a.clear();
for (size_t i = 0; i < down.size(); i++)
a.pb(down[i]);
for (size_t i = up.size() - 2; i > 0; i--)
a.pb(up[i]);
}
int main()
{
freopen("infasuratoare.in", "r", stdin);
freopen("infasuratoare.out", "w", stdout);
scanf("%d", &n);
vector <pt> a;
for (int i = 1; i <= n; i++)
{
pt curr;
scanf("%lf%lf", &curr.x, &curr.y);
a.pb(curr);
}
convex_hull(a);
printf("%d\n", a.size());
for (size_t i = 0; i < a.size(); i++)
printf("%.8lf %.8lf\n", a[i].x, a[i].y);
return 0;
}