Cod sursa(job #2233852)

Utilizator PetyAlexandru Peticaru Pety Data 24 august 2018 16:13:39
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.03 kb
#include<bits/stdc++.h>
#define x first
#define y second
#define P pair<double, double>

using namespace std;

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

int n;
pair<double, double>v[120002], minn;
int poz;

double lol (P p, P a, P b) {
  return (a.x - p.x) * (b.y - p.y) - (a.y - p.y) * (b.x - p.x);
}

bool cmp (P x, P y) {
  return lol(v[1], x, y) < 0;
}

P st[120002];

int main()
{
  fin >> n;
  for (int i = 1; i <= n; i++) {
    fin >> v[i].x >> v[i].y;
  }
  poz = 1;
  minn = v[1];
  for (int i = 1; i <= n; i++) {
    if (v[i] < minn) {
      minn = v[i];
      poz = i;
    }
  }
  swap(v[1], v[poz]);
  sort(v + 2, v + n + 1, cmp);
  st[1] = v[1];
  st[2] = v[2];
  int vf = 2;
  for (int i = 3; i <= n; i++) {
    while (vf >= 2 && lol(st[vf - 1], st[vf], v[i]) > 0)
      vf--;
    st[++vf] = v[i];
  }
  fout << vf << "\n";
  for (int i = vf; i >= 1; i--) {
    fout << fixed << setprecision(6) << st[i].x << " " << st[i].y << "\n";
  }
  return 0;
}