Cod sursa(job #2957281)

Utilizator YusyBossFares Yusuf YusyBoss Data 22 decembrie 2022 11:22:48
Problema Infasuratoare convexa Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.51 kb
#include <bits/stdc++.h>
#define NMAX 120000
#define XYMAX 1000000000
#define CW -1
#define COL 0
#define CCW 1

using namespace std;

ifstream fin ("infasuratoare.in");
ofstream fout ("infasuratoare.out");

struct punct {
  double x, y;

  bool operator == (const punct &A) const {
    return (A.x == x && A.y == y);
  }
};

punct lowest;
punct v[NMAX + 1];

int get_orientation(punct A, punct B, punct C) {
  int val = (B.y - A.y) * (C.x - B.x) - (B.x - A.x) * (C.y - B.y);

  if (val < 0)
    return CCW;
  else if (val == 0)
    return COL;
  else
    return CW;
}

bool cmp(punct A, punct B) {
  if (A == lowest)
    return 1;
  if (B == lowest)
    return 0;
  /// le sortez astfel incat lowest sa fie primul

  return get_orientation(lowest, A, B) == CCW;
}

int main() {
  int n, i;
  fin >> n;

  lowest.x = lowest.y = XYMAX + 1;
  for (i = 0; i < n; i++) {
    fin >> v[i].x >> v[i].y;

    if (v[i].x < lowest.x || (v[i].x == lowest.x && v[i].y < lowest.y))
      lowest.x = v[i].x, lowest.y = v[i].y;
  }

  sort(v, v + n, cmp);

  vector < punct > stiva;
  stiva.push_back( lowest );

  for (i = 1; i < n; i++) {
    while (stiva.size() > 1 && get_orientation(stiva[stiva.size() - 2], stiva[stiva.size() - 1], v[i]) == CW)
      stiva.pop_back();
    stiva.push_back(v[i]);
  }

  fout << stiva.size() << "\n";
  for (i = 0; i < stiva.size(); i++) {
    fout << fixed << setprecision(6) << (double)stiva[i].x << " " << (double)stiva[i].y << "\n";
  }
  return 0;
}