Cod sursa(job #3131273)

Utilizator AlexandruBenescuAlexandru Benescu AlexandruBenescu Data 19 mai 2023 17:29:51
Problema Infasuratoare convexa Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.2 kb
#include <bits/stdc++.h>
#define L 120005
#define EPS 0.0000000001
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");

struct MS{
  float x;
  float y;
};

int n;
MS v[L];
int st[L], ind;
vector <int> ans;

bool cmp(const MS &a, const MS &b){
  return a.x < b.x;
}

double area(int i1, int i2, int i3){
  double a = v[i1].x;
  double b = v[i1].y;
  double c = v[i2].x;
  double d = v[i2].y;
  double e = v[i3].x;
  double f = v[i3].y;
  return (a * d + b * e + c * f  - a * f - b * c - d * e) / 2;
}

int main(){
  fin >> n;
  for (int i = 1; i <= n; i++)
    fin >> v[i].x >> v[i].y;
  sort (v + 1, v + n + 1, cmp);
  for (int i = 1; i <= n; i++){
    while (ind > 1 && area(st[ind - 2], st[ind - 1], i) > -EPS)
      ind--;
    st[ind++] = i;
  }
  for (int i = ind - 1; i > 0; i--)
    ans.push_back(st[i]);
  ind = 0;
  for (int i = 1; i <= n; i++){
    while (ind > 1 && area(st[ind - 2], st[ind - 1], i) < EPS)
      ind--;
    st[ind++] = i;
  }
  for (int i = 0; i < ind - 1; i++)
    ans.push_back(st[i]);
  fout << ans.size() << "\n";
  for (auto it : ans)
    fout << v[it].x << " " << v[it].y << "\n";
  return 0;
}