Cod sursa(job #589713)

Utilizator dushmiMihai-Alexandru Dusmanu dushmi Data 13 mai 2011 15:26:04
Problema Rubarba Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.66 kb
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <fstream>

using namespace std;

struct pct {
  double x, y;
};

const int N = 100005;

pct v[N];

int n, st[N];

bool f[N];

void read() {
  scanf("%d", &n);

  for (int i = 1; i <= n; ++ i)
    scanf("%lf%lf", &v[i].x, &v[i].y);
}

bool comp(const pct &A, const pct &B) {
  if (A.x < B.x) return true;
  if (A.x > B.x) return false;
  return A.y < B.y;
}

double arie(double x1, double y1, double x2, double y2, double x3, double y3) {
  return x1 * y2 + x2 * y3 + x3 * y1 - y2 * x3 - y3 * x1 - y1 * x2;
}

double semn(int i, int j, int k) {
  return arie(v[i].x, v[i].y, v[j].x, v[j].y, v[k].x, v[k].y);
}

void vertex_cover()
{
  sort(v + 1, v + n + 1, comp);

  st[++ st[0]] = 1;
  f[1] = true;
  st[++ st[0]] = 2;
  f[2] = true;

  for (int i = 3; i <= n; ++ i)	{
    while (semn(st[st[0]], st[st[0] - 1], i) <= 0 && st[0] > 1) {
      f[st[st[0]]] = false;
      -- st[0];
    }

    st[++ st[0]] = i;
    f[i] = true;
  }

  for (int i = n; i >= 1; -- i)
    if (f[i] == false || i == 1) {
      while (semn(st[st[0]], st[st[0] - 1], i) <= 0 && st[0] > 1) {
        f[st[st[0]]] = false;
        -- st[0];
      }

      st[++ st[0]] = i;
      f[i] = true;
  }

}

const double INF = 1000000000000000.00;

inline double dist_pct_dr(double a, double x, double b, double c, int i) {
  if (a == INF)
    return v[i].x - x;
  return ((a * v[i].x + b * v[i].y + c) / sqrt(a * a + b * b));
}

inline double modul(double x) {
  return x < 0 ? (- x) : x;
}

void solve() {
  pct A, B;

  double rez = INF, lung, lat, a1, b1, c1, a2, b2, c2, m1, m2, maxd, mind;

  for (int i = 1; i < st[0]; ++ i) {
    A = v[st[i]];
    B = v[st[i + 1]];

    if (A.x == B.x)
      a1 = m1 = INF;
    else
      a1 = m1 = (double)(B.y - A.y) / (B.x - A.x);
    b1 = - 1;
    c1 = A.y - m1 * A.x;

    maxd = - INF;
    for (int j = 1; j < st[0]; ++ j)
      if (modul(dist_pct_dr(a1, A.x, b1, c1, st[j])) > maxd)
        maxd = modul(dist_pct_dr(a1, A.x, b1, c1, st[j]));
    lung = maxd;

    if (m1 == 0)
      a2 = m2 = INF;
    else
      a2 = m2 = - (double)1 / m1;
    b2 = - 1;
    c2 = A.y - m2 * A.x;

    mind = INF;
    maxd = - INF;
    for (int j = 1; j < st[0]; ++ j) {
      if (dist_pct_dr(a2, A.x, b2, c2, st[j]) < mind)
        mind = dist_pct_dr(a2, A.x, b2, c2, st[j]);
      if (dist_pct_dr(a2, A.x, b2, c2, st[j]) > maxd)
        maxd = dist_pct_dr(a2, A.x, b2, c2, st[j]);
    }
    lat = maxd - mind;

    if (lung > 0 && lat > 0 && lung * lat < rez)
      rez = lung * lat;
  }

  printf("%lf", rez);
}

int main() {
  freopen("rubarba.in", "r", stdin);
  freopen("rubarba.out", "w", stdout);

  read();

  vertex_cover();

  solve();

  return 0;
}