Cod sursa(job #2957583)

Utilizator Remus.RughinisRemus Rughinis Remus.Rughinis Data 22 decembrie 2022 22:03:06
Problema Infasuratoare convexa Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.68 kb
#include <iostream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#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;
}

bool sortCompare(EdgeDegree a, EdgeDegree b){
  double left = a.upper * b.lower;
  double right = a.lower * b.upper;

  if(a.minus && !b.minus)
    return true;
  if(!a.minus && b.minus)
    return false;

  if(a.minus && b.minus)
    return left > right;

  return left < right;
}

/*
  -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; 

  // printf("%f %f\n", p[0].x, p[0].y);

  // 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].end = p[i];

    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 = true;
    }
  }
  // quicksort(0, n-2);
  sort(v, v + n-1, sortCompare);

  i = 0;
  while(v[i].minus && i < n-1)
    i ++;

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

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

  // 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;
}