Cod sursa(job #2953612)

Utilizator iraresmihaiiordache rares mihai iraresmihai Data 11 decembrie 2022 19:32:44
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.44 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>

#define MAXN 120000
#define EPSILON 0.000000000001
using namespace std;

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

struct point{
  double x, y;
};

point p0;
point v[MAXN];
point ans[MAXN];
int ansSize;

bool comp(point a, point b) {
  return (p0.y - a.y) * (p0.x - b.x) - (p0.y - b.y) * (p0.x - a.x) <= EPSILON;
}

bool isTrigonometricWay(point a, point b, point c) {
  return (a.y - b.y) * (b.x - c.x) - (b.y - c.y) * (a.x - b.x) <= EPSILON;
}

int main() {
  int n, i, posOfP0;

  fin >> n;

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

    if ( v[posOfP0].y > v[i].y )
      posOfP0 = i;
  }
  p0.x = v[posOfP0].x;
  p0.y = v[posOfP0].y;
  v[posOfP0].x = v[n - 1].x;
  v[posOfP0].y = v[n - 1].y;

  sort(v, v + n - 1, comp);
  ansSize = 3;
  ans[0].x = p0.x;
  ans[0].y = p0.y;
  ans[1].x = v[0].x;
  ans[1].y = v[0].y;
  ans[2].x = v[1].x;
  ans[2].y = v[1].y;

  for ( i = 2; i < n - 1; i++ ) {
    while ( !isTrigonometricWay(ans[ansSize - 2], ans[ansSize - 1], v[i]) )
      ansSize--;
    ans[ansSize].x = v[i].x;
    ans[ansSize].y = v[i].y;
    ansSize++;
  }

  fout << setprecision(15);
  fout << ansSize << "\n";
  for ( i = 0; i < ansSize; i++ ) {
    fout << ans[i].x << " " << ans[i].y << "\n";
  }

  fin.close();
  fout.close();

  return 0;
}