Cod sursa(job #1873097)

Utilizator cella.florescuCella Florescu cella.florescu Data 8 februarie 2017 19:43:12
Problema Rubarba Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.35 kb
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e5;

pair <int, int> v[3 * MAXN], aux[MAXN];

inline long long ccw(pair <int, int> A, pair <int, int> B, pair <int, int> C) {
  return 1LL * (B.first - A.first) * (C.second - A.second) - 1LL * (B.second - A.second) * (C.first - A.first);
}

bool cmp(pair <int, int> A, pair <int, int> B) {
  return ccw(aux[0], A, B) > 0LL;
}

struct Stuff {
  double a, b, c;
  void init(pair <int, int> X, pair <int, int> Y) {
    a = Y.second - X.second;
    b = X.first - Y.first;
    c = 1LL * X.second * Y.first - 1LL * X.first * Y.second;
    double x = sqrt(a * a + b * b);
    a /= x;
    b /= x;
    c /= x;
  }
  double dist(pair <int, int> P) {
    return a * P.first + b * P.second + c;
  }
  void initp(Stuff d, pair <int, int> P) {
    a = -d.b;
    b = d.a;
    c = -a * P.first - b * P.second;
    double x = sqrt(a * a + b * b);
    a /= x;
    b /= x;
    c /= x;
  }
} dr, drp;

int main()
{
    double area;
    int n, st, r, u, l;
    ifstream fin("rubarba.in");
    fin >> st;
    for (int i = 0; i < st; ++i)
      fin >> aux[i].first >> aux[i].second;
    fin.close();
    for (int i = 1; i < st; ++i)
      if (aux[i] < aux[0])
        swap(aux[i], aux[0]);
    sort(aux, aux + st, cmp);
    n = 0;
    for (int i = 0; i < st; ++i) {
      while (n > 1 && ccw(v[n - 2], v[n - 1], aux[i]) < 0LL)
        --n;
      v[n++] = aux[i];
    }
    for (int i = 0; i < n; ++i)
      v[i + n] = v[i + 2 * n] = v[i];
    dr.init(v[n - 1], v[0]);
    drp.initp(dr, v[n - 1]);
    u = l = 0;
    while (dr.dist(v[u + 1]) < dr.dist(v[u]))
      ++u;
    while (drp.dist(v[l + 1]) > drp.dist(v[l]))
      ++l;
    r = n - 1;
    while (drp.dist(v[r - 1]) < drp.dist(v[r]))
      --r;
    area = abs(dr.dist(v[u])) * (drp.dist(v[l]) + abs(drp.dist(v[r])));
    for (int i = 0; i < n - 1; ++i) {
      dr.init(v[i], v[i + 1]);
      drp.initp(dr, v[i]);
      while (drp.dist(v[l + 1]) > drp.dist(v[l]))
        ++l;
      while (drp.dist(v[r + 1]) < drp.dist(v[r]))
        ++r;
      while (dr.dist(v[u + 1]) < dr.dist(v[u]))
        ++u;
      area = min(area, abs(dr.dist(v[u])) * (drp.dist(v[l]) + abs(drp.dist(v[r]))));
    }
    ofstream fout("rubarba.out");
    fout << setprecision(2) << fixed << area << '\n';
    fout.close();
    return 0;
}