Cod sursa(job #462696)

Utilizator mgntMarius B mgnt Data 12 iunie 2010 22:16:12
Problema Rubarba Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.55 kb
#include <fstream>
#include <algorithm>
using namespace std;

struct Pt
{
  int x, y;
  bool operator < (Pt const & o)
  {
    return (x<o.x) || ((x==o.x) && (y<o.y));
  }
  bool operator == (Pt const & o)
  {
    return (x==o.x) && (y ==o.y);
  }
};

typedef long long ll;

ll cross(Pt const & O, Pt const & A, Pt const & B)
{
  return (A.x-O.x)*(B.y-O.y)-(A.y-O.y)*(B.x-O.x);
}

// Andrew's Monotone Chain Convex Hull algorithm
void convexHull(Pt * P, int n, Pt * H, int & m)
{
  // Sort increasing on x, then on y
  make_heap(&P[0],&P[n]);
  sort_heap(&P[0],&P[n]);
  // Build lower hull
  int k=0;
  int i;
  for (i=0;n>i;++i)
  {
    while ((2<=k) && (0>=cross(H[k-2],H[k-1],P[i]))) --k;
    H[k++]=P[i];
  }
  // Build upper hull
  int t=k+1;
  for (i=n-2;0<i; --i) /* #@ */
  {
    while ((t<=k) && (0<=cross(P[i], H[k-1], H[k-2]))) --k;
    H[k++]=P[i];
  }
  // #@: H uses at most n locations.
  while ((t<=k) && (0<=cross(P[0],H[k-1],H[k-2]))) --k;
  m=k;
}

bool less2(ll p1, ll q1, ll p2, ll q2)
{
  ll u1 = p1/q1, u2 = p2/q2;
  if (u1 != u2) return u1<u2;
  p1 = p1%q1; p1 *= 10; ll z1 = p1/q1;
  p2 = p2%q2; p2 *= 10; ll z2 = p2/q2;
  if (z1 != z2) return z1<z2;
  p1 = p1%q1; p1 *= 10; ll s1 = p1/q1;
  p2 = p2%q2; p2 *= 10; ll s2 = p2/q2;
  return s1 < s2;
}

void print2(ostream & os, ll p, ll q)
{
  ll u = p/q;
  p = p%q; p *= 10; ll z = p/q;
  p = p%q; p *= 10; ll s = p/q;
  os << u << '.' << z << s << endl;
}

bool up(Pt & p1, Pt & p2, Pt & p3, Pt & p4)
{
  ll u = p2.x-p1.x, w = p2.y-p1.y;
  ll s = p4.x-p3.x, t = p4.y-p3.y;
  ll cp = u*t-w*s;
  return 0<cp;
}

void computeArea(Pt & p1, Pt & p2, Pt & p3, Pt & p4, Pt & p5, ll & p, ll & q)
{
  ll xu = p2.x - p3.x, xw = p3.y - p2.y, yu = -xw, yw = xu;
  ll lx = (p4.x-p3.x) * xu + (p4.y-p3.y) * yu;
  ll rx = (p1.x-p3.x) * xu + (p1.y-p3.y) * yu;
  ll by = 0;
  ll ty = (p5.x-p3.x) * xw + (p5.y-p3.y) * yw;
  p = (rx-lx) * (ty-by);
  q = xu*xu + xw*xw;
}

void wrap(Pt * H, int m, ll & p, ll & q)
{
  int b, t; ll p0, q0=0, p1, q1;
  for (b=m-1, t=b-1; 0 <= b; --b)
  {
    while (up(H[b],H[(b+1)%m],H[t],H[(t+m-1)%m])) { t=(t+m-1)%m; }
    computeArea(H[(b+2)%m],H[(b+1)%m],H[b],H[(b+m-1)%m],H[t],p1, q1);
    if ( (0 == q0) || less2(p1,q1,p0,q0) ) { p0 = p1; q0 = q1; }
  }
  p=p0; q=q0;
}

int const maxn = 100 * 1000; Pt P[maxn], H[maxn];

int main()
{
  ifstream is("rubarba.in");
  ofstream os("rubarba.out");
  int n, m, i;
  is >> n;
  for (i=0;n>i;++i)
  {
    is>>P[i].x>>P[i].y;
  }
  convexHull(P,n,H,m);
  if (3 > m)
  {
    os<<"0.00"<<endl;
  }
  else
  {
    ll p, q;
    wrap(H,m,p,q);
    print2(os,p,q);
  }
  return 0;
}