Cod sursa(job #3338639)

Utilizator IanisBelu Ianis Ianis Data 4 februarie 2026 13:01:24
Problema Infasuratoare convexa Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.31 kb
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ld = long double;

#define int ll
#define double ld

const int NMAX = 1.2e5+5;

struct Point {
   double x, y;
};

int n;
Point a[NMAX];
set<pair<double, double>> s;

int dist(const Point &a, const Point &b) {
   return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}

int det(const Point &a, const Point &b, const Point &c) {
   return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
   return a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y);
}

void read() {
   cin >> n;
   for (int i = 1; i <= n; i++) {
      cin >> a[i].x >> a[i].y;
      if (s.count({ a[i].x, a[i].y })) {
         i--;
         n--;
      } else {
         s.emplace(a[i].x, a[i].y);
      }
   }
}

void solve() {
   a[0] = a[1];
   for (int i = 2; i <= n; i++) {
      if (a[i].y < a[0].y || (a[i].y == a[0].y && a[i].x < a[0].x)) {
         a[0] = a[i];
      }
   }

   sort(a + 1, a + n + 1, [&](const Point &p1, const Point &p2) {
      int d = det(a[0], p1, p2);
      if (d == 0) return dist(a[0], p1) < dist(a[0], p2);
      return d < 0;
   });

   vector<Point> hull = { a[1], a[2] };

   for (int i = 3; i <= n; i++) {
      while (hull.size() > 1 && det(hull[hull.size() - 2], hull.back(), a[i]) > 0) {
         hull.pop_back();
      }
      hull.push_back(a[i]);
   }

   reverse(hull.begin(), hull.end());

   cout << hull.size() << endl;
   for (auto [ x, y ] : hull) {
      cout << setprecision(6) << fixed << x << ' ' << y << '\n';
   }
#if 0
   n = hull.size();
   int ans = 0;

   for (int i = 0, j = 0; i < n; i++) {
      ans = max(ans, dist(hull[i], hull[j]));
      while (dist(hull[i], hull[j]) < dist(hull[i], hull[(j + 1) % n])) {
         j = (j + 1) % n;
         ans = max(ans, dist(hull[i], hull[j]));
      }
      for (int k = -500; k <= 500; k++) {
         ans = max(ans, dist(hull[i], hull[(j + k + 1000ll * n) % n]));
      }
   }

   return sqrtl(ans);
#endif
}

signed main() {
#ifdef LOCAL
   freopen("input.txt", "r", stdin);
#else
   freopen("infasuratoare.in", "r", stdin);
   freopen("infasuratoare.out", "w", stdout);
#endif

   ios_base::sync_with_stdio(false);
   cin.tie(0);
   cout.tie(0);

   read();
   solve();

   return 0;
}