Cod sursa(job #2955844)

Utilizator Remus.RughinisRemus Rughinis Remus.Rughinis Data 17 decembrie 2022 22:32:46
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.32 kb
#include <iostream>
#include <fstream>
#include <iomanip>
#define MAXN 120000
#define MAXVAL 2000000000

using namespace std;

struct Point{
  double x;
  double y;

  int id;
};
struct EdgeDegree{
  double upper;
  double lower;

  Point end;
};

EdgeDegree v[MAXN];
Point p[MAXN];

int compare(int a, int b){
  if(a > b)
    return 1;
  if(a == b)
    return 0;
  return -1;
}

static inline int quickCompare(int a, int b){
  return compare(v[a].upper * v[b].lower, v[a].lower * v[b].upper);
}
void quicksort(int begin, int end){
  int b = begin, e = end, piv = (begin + end) / 2;
  EdgeDegree aux;

  if(quickCompare(b, piv) == -1) // b < piv
    b ++;
  if(quickCompare(e, piv) == 1) // e > piv
    e --;

  while(b < e){
    aux = v[b];
    v[b] = v[e];
    v[e] = aux;

    do{
      b ++;
    } while(quickCompare(b, piv) == -1); // b < piv
    do{
      e --;
    } while(quickCompare(e, piv) == 1); // e > piv
  }

  if(e > begin)
    quicksort(begin, e);
  if(e + 1 < end)
    quicksort(e + 1, end);
}

/*
  -1 = clockwise
   0 = colineare
   1 = ordine trigonometrica
*/
int getOrient(Point a, Point b, Point c){
  int st = (a.y - b.y) * (b.x - c.x);
  int dr = (b.y - c.y) * (a.x - b.x);
  return compare(st, dr);
}

Point stv[MAXN];
int dr;

int main(){
  int n, i, j, x, y, minp;
  Point min;

  ifstream fin ("infasuratoare.in");
  fin >> n;

  min = {MAXVAL, MAXVAL};
  minp = 0;
  for(i = 0; i < n; i ++){
    fin >> p[i].x >> p[i].y;
    p[i].id = i;

    if(p[i].y < min.y || (p[i].y == min.y && p[i].x < min.x)){
      min = p[i];
      minp = i;
    }
  }
  fin.close();

  Point aux = p[0];
  p[0] = p[minp];
  p[minp] = p[0];

  // Punctul reper este acum p[0]
  for(i = 1; i < n; i ++){
    v[i - 1].upper = p[i].y - p[0].y ;
    v[i - 1].lower = p[i].x - p[0].x;
    v[i - 1].end = p[i];
  }
  quicksort(0, n-2);

  // for(i = 0; i < n - 1; i ++){
  //   printf("%d: %.1f / %.1f\n", v[i].end.id, v[i].upper, v[i].lower);
  // }
  // printf("\n");

  dr = 1;
  stv[0] = p[0];

  for(i = 0; i < n - 1; i ++){
    while(dr > 1 && getOrient(stv[dr - 2], stv[dr - 1], v[i].end) != -1)
      dr --;

    stv[dr] = v[i].end;
    dr ++;
  }

  ofstream fout ("infasuratoare.out");
  fout << dr << endl;

  fout << fixed;
  fout << setprecision(6);
  for(i = 0; i < dr; i ++)
    fout << stv[i].x << " " << stv[i].y << endl;
  fout.close();

  return 0;
}