Cod sursa(job #1043856)

Utilizator AnonymouslegionAnonymous Anonymouslegion Data 28 noiembrie 2013 23:29:37
Problema Rubarba Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.48 kb
#include <fstream>
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <cmath>

using namespace std;

class point{
public:
  double x, y;

  point(){};

  point(double x1, double y1){
    x = x1;
    y = y1;
  }

  bool operator ==(point other){
    return (x == other.x) && (y == other.y);
  }

  point operator +(point other){
    return point(x + other.x, y + other.y);
  }

  point operator -(point other){
    return point(x - other.x, y - other.y);
  }
};

point refer;

double ccw(point a, point b, point c){
  return 0.5 * (c.y * (b.x - a.x) + b.y * (a.x - c.x) + a.y * (c.x - b.x)); // C is to the left of AB returns positive
}

double dist(point a, point b){
  return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}

point rot(point x){
  return point(x.y, -x.x);
}

point cntclck(point a, point lefi){
  point t(a.x, a.y);
  t = t - lefi;
  t = rot(t);
  t = t + lefi;
  return t;
}

double dst(point x, point a, point b){
  return fabs(ccw(a, b, x)) * 2.0 / dist(a, b);
}

int cmp(point a, point b){
  if(b == refer)
    return 0;
  if(a == refer)
    return 1;

  if(ccw(refer, a, b) == 0)
    return dist(refer, a) < dist(refer, b);

  return ccw(refer, a, b) > 0;
}

int n;
vector<point> gv;
vector<int> hull;

void get_hull(){
  for(int i = 1; i < n; ++i)
    if(gv[i].x < gv[0].x)
      swap(gv[i], gv[0]);
    else if(gv[i].x == gv[0].x && gv[i].y < gv[0].y)
      swap(gv[i], gv[0]);

  refer = gv[0];

  sort(gv.begin(), gv.end(), cmp);

  for(int i = n - 2; i > 0; --i)
    if(ccw(gv[i], gv[i + 1], refer) != 0){
      for(int j = i + 1, k = n - 1; j < k; ++j, --k)
        swap(gv[j], gv[k]);
      break;
  }

  hull.push_back(0);
  int u = 1;
  gv.push_back(gv[0]);

  for(int i = 1; i < gv.size(); ++i){
    hull.push_back(i);
    ++u;

    while(u >= 3)
      if(ccw(gv[hull[u - 3]], gv[hull[u - 2]], gv[hull[u - 1]]) <= 0){
        hull[u - 2] = hull[u - 1];
        --u;
        hull.pop_back();
      }
      else
        break;
  }

  hull.pop_back();
}

int nx(int x){
  return (x + 1) % hull.size();
}

int prv(int x){
  return (x + hull.size() - 1) % hull.size();
}

int main(){
  ifstream in("rubarba.in");
  ofstream out("rubarba.out");

  in >> n;
  for(int i = 1; i <= n; ++i){
    double x, y;
    in >> x >> y;
    gv.push_back(point(x, y));
  }

  get_hull();

  int up = 1, lef = 1, rai = 0;

  point help = cntclck(gv[hull[1]], gv[hull[0]]);

  while(dst(gv[hull[prv(rai)]], gv[hull[0]], help) >= dst(gv[hull[rai]], gv[hull[0]], help))
    rai = prv(rai);
  while(dst(gv[hull[nx(lef)]], gv[hull[0]], help) >= dst(gv[hull[lef]], gv[hull[0]], help))
    lef = nx(lef);
  while(dst(gv[hull[nx(up)]], gv[hull[0]], gv[hull[1]]) >= dst(gv[hull[up]], gv[hull[0]], gv[hull[1]]))
    up = nx(up);

  double ans = 2e9;

  for(int i = 0; i < hull.size(); ++i){
    help = cntclck(gv[hull[nx(i)]], gv[hull[i]]);
    point a = gv[hull[i]], b = gv[hull[nx(i)]];

    while(dst(gv[hull[nx(up)]], a, b) >= dst(gv[hull[up]], a, b))
      up = nx(up);


    while(ccw(a, help, gv[hull[rai]]) > 0)
      rai = nx(rai);
    while(dst(gv[hull[nx(rai)]], a, help) >= dst(gv[hull[rai]], a, help) && ccw(a, help, gv[hull[nx(rai)]]) < 0)
      rai = nx(rai);

    while(ccw(a, help, gv[hull[lef]]) < 0)
      lef = nx(lef);
    while(dst(gv[hull[nx(lef)]], a, help) >= dst(gv[hull[lef]], a, help) && ccw(a, help, gv[hull[nx(lef)]]) > 0)
      lef = nx(lef);

    ans = min(ans, (dst(gv[hull[lef]], a, help) + dst(gv[hull[rai]], a, help)) * dst(gv[hull[up]], a, b));
  }

  out << ans;

  return 0;
}