Cod sursa(job #2562245)

Utilizator popashtefan10Popa Stefan popashtefan10 Data 29 februarie 2020 13:02:27
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.45 kb
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#define NMAX 120000

using namespace std;

const double INF = 200000000000;

struct point {
  double x, y;
} p[NMAX + 5];

int n, vf;
point st[NMAX + 5];

double panta(point p1, point p2) {
  if(p1.x == p2.y) {
    if(p1.y < p2.y)
      return INF;
    return -INF;
  }
  return (p2.y - p1.y) / (p2.x - p1.x);
}

bool cmp(point p1, point p2) {
  double m1 = panta(p[1], p1), m2 = panta(p[1], p2);

  if(m1 != m2)
    return m1 < m2;
  if(m1 < 0)
    return p1.x < p2.x;
  return p1.x > p2.x;
}

double det(point p1, point p2) {
  return p1.x * p2.y - p1.y * p2.x;
}

double cross_product(point p1, point p2, point p3) {
  return det(p2, p3) - det(p1, p3) + det(p1, p2);
}

int main() {
  freopen("infasuratoare.in", "r", stdin);
  freopen("infasuratoare.out", "w", stdout);
  int pozmin;
  double minx = INF;

  scanf("%d ", &n);
  for(int i = 1; i <= n; i++) {
    scanf("%lf %lf ", &p[i].x, &p[i].y);
    if(p[i].x < minx) {
      minx = p[i].x;
      pozmin = i;
    }
  }

  if(pozmin > 1)
    swap(p[pozmin], p[1]);
  sort(p + 2, p + n + 1, cmp);

  vf = 0;
  st[++vf] = p[1];
  for(int i = 2; i <= n; i++) {
    while(vf > 1 && cross_product(st[vf - 1], st[vf], p[i]) < 0)
      vf--;
    st[++vf] = p[i];
  }

  printf("%d\n", vf);
  for(int i = 1; i <= vf; i++)
    printf("%f %f\n", st[i].x, st[i].y);

  return 0;
}