Cod sursa(job #2955985)

Utilizator Remus.RughinisRemus Rughinis Remus.Rughinis Data 18 decembrie 2022 14:15:26
Problema Infasuratoare convexa Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.85 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;
  bool minus = false;

  Point end;
};

EdgeDegree v[MAXN], u[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){
  if(v[a].minus && !v[b].minus)
    return -1;
  if(v[b].minus && !v[a].minus)
    return 1;

  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 = (b + e) / 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, minp, j;
  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] = aux; 

  // Punctul reper este acum p[0]
  for(i = 1; i < n; i ++){
    v[i - 1].upper = p[i].y - p[0].y;
    if(v[i-1].upper < 0){
      v[i-1].upper = -v[i-1].upper;
      v[i-1].minus = !v[i-1].minus;
    }

    v[i - 1].lower = p[i].x - p[0].x;
    if(v[i-1].lower < 0){
      v[i-1].lower = -v[i-1].lower;
      v[i-1].minus = !v[i-1].minus;
    }

    v[i - 1].end = p[i];
  }
  quicksort(0, n-2);

  i = 0;
  while(v[i].minus && i < n - 1){
    u[n - 2 - i] = v[i];
    i ++;
  }
  j = i;
  while(j < n-1){
    u[j - i] = v[j];
    j ++;
  }

  // printf("\n");
  // for(i = 0; i < n - 1; i ++){
  //   printf("%d: ", u[i].end.id);
  //   if(u[i].minus)
  //     printf("- ");
  //   printf("%.1f / %.1f\n", u[i].upper, u[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], u[i].end) != -1)
      dr --;

    stv[dr] = u[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;
}