Cod sursa(job #2878955)

Utilizator FunnyStockyMihnea Andreescu FunnyStocky Data 28 martie 2022 10:46:24
Problema Infasuratoare convexa Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.47 kb
#include <iostream>
#include <vector> 
#include <algorithm> 
#include <string> 
#include <cassert> 
#include <algorithm> 
#include <set> 
#include <iomanip> 
#include <queue> 
#include <deque> 
#include <unordered_set> 
#include <unordered_map> 
#include <functional> 
#include <cmath> 
#include <map> 
#include <random> 
#include <chrono> 
#include <cstdio> 

using namespace std;

typedef double ld;

class Vector {
public:
  ld x, y;
};

Vector operator + (Vector a, Vector b) { return { a.x + b.x, a.y + b.y }; }
Vector operator - (Vector a, Vector b) { return { a.x - b.x, a.y - b.y }; }
Vector operator * (Vector a, ld b) { return { a.x * b, a.y * b }; }
Vector operator / (Vector a, ld b) { return { a.x / b, a.y / b }; }
Vector operator * (ld b, Vector a) { return { a.x * b, a.y * b }; }
ld dot(Vector a, Vector b) { return  a.x * b.x + a.y * b.y; }
ld cross(Vector a, Vector b) { return a.x * b.y - a.y * b.x; }
ld get_norm(Vector a) { return sqrt(a.x * a.x + a.y * a.y); }
Vector normalize(Vector a) { return a / get_norm(a); }
ld getArea(Vector a, Vector b) { return (a.x + b.x) * (a.y - b.y); }
ld getArea(Vector a, Vector b, Vector c) { return getArea(a, b) + getArea(b, c) + getArea(c, a); }

Vector spec;
bool operator < (Vector p1, Vector p2) {
  return getArea(spec, p1, p2) < 0;

}

class Hulk {
private:

public:
  vector<Vector> Hulkize(vector<Vector> points) {
    assert(!points.empty());
    int n = (int)points.size();
    for (int i = 1; i < n; i++) {
      if (points[i].x < points[0].x) {
        swap(points[i], points[0]);
      }
      else {
        if (points[i].x == points[0].x && points[i].y < points[0].y) {
          swap(points[i], points[0]);
        }
      }
    }
    spec = points[0];
    sort(points.begin() + 1, points.end());
    points.push_back(points[0]);
    vector<Vector> sol;
    for (auto& p : points) {
      while ((int)sol.size() >= 2 && getArea(sol[(int)sol.size() - 2], sol[(int)sol.size() - 1], p) > 0) {
        sol.pop_back();
      }
      sol.push_back(p);
    }
    return sol;
  }
};


signed main() {
  freopen("infasuratoare.in", "r", stdin);
  freopen("infasuratoare.out", "w", stdout);

  int n;
  cin >> n;
  vector<Vector> v(n);
  for (auto& p : v) {
    cin >> p.x >> p.y;
  }
  Hulk hulk;
  v = hulk.Hulkize(v);
  v.pop_back();
  cout << (int)v.size() << "\n";
  for (auto& p : v) {
    cout << fixed << setprecision(6) << p.x << " " << p.y << "\n";
  }

}