Cod sursa(job #1977497)

Utilizator GoogalAbabei Daniel Googal Data 5 mai 2017 12:49:18
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.69 kb
#include <fstream>
#include <algorithm>
#include <iomanip>
#define err 1e-12

using namespace std;

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

const int NMAX = 120000;

struct data{
  double x;
  double y;
};

int n, h, last, q, st[1 + NMAX], ok[1 + NMAX];
data v[1 + NMAX];

int check(double a, double b){
  if(a + err < b)
    return 1;
  else if(b + err < a)
    return -1;
  return 0;
}

bool cmp(data a, data b){
  int answer = check(a.x, b.x);
  if(answer != 0){
    return (answer == 1);
  }else{
    return(check(a.y, b.y) == 1);
  }
}

int sgn(data a, data b, data c){
  double x1, y1, z1;
  x1 = a.y - b.y;
  y1 = b.x - a.x;
  z1 = a.x * b.y - b.x * a.y;

  return check(x1 * c.x + y1 * c.y + z1, 0);
}

void solve(){
  int node;
  sort(v + 1, v + n + 1, cmp);

  st[1] = 1;
  st[2] = 2;
  ok[2] = 1;
  node = 3;
  last = 2;
  q = 1;

  while(ok[1] == 0){
    while(ok[node]){
      if(node == n)
        q = -1;
      node += q;
    }

    while(last >= 2 && sgn(v[st[last - 1]], v[st[last]], v[node]) == -1){
      ok[st[last]] = 0;
      last--;
    }
    st[++last] = node;
    ok[node] = 1;
  }
  h = last - 1;

}

void write(){
  out << h << '\n';
  out << setprecision(6) << fixed;
  for(int i = h; i >= 2; i--){
    out << v[st[i]].x << ' ' << v[st[i]].y << '\n';
  }

  out << v[st[h + 1]].x << ' ' << v[st[h + 1]].y << '\n';
  //for(int i = 2; i <= h + 1; i++){
   // out << st[i] << ' ';// << ' ' << v[st[i]].y << '\n';
  //}
}

int main()
{
  in >> n;
  for(int i = 1; i <= n; i++){
    in >> v[i].x >> v[i].y;
  }
  in.close();

  solve();
  write();
  out.close();
  return 0;
}