Cod sursa(job #462811)

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

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

typedef long long ll;
typedef long double ld;

ll cross(Pt const & O, Pt const & A, Pt const & B)
{
  return ll(A.x-O.x)*ll(B.y-O.y)-ll(A.y-O.y)*ll(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 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;
}

ll lr(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 = (-w)*t-u*s;
  return cp;
}

ld computeArea(Pt & p1, Pt & p2, Pt & p3, Pt & p4, Pt & p5)
{
  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;
  ld e = ld(rx-lx) * ld(ty-by);
  ld f = ld(xu*xu + xw*xw);
  return e/f;
}

ld wrap(Pt * H, int m)
{
  int b, t, l, r, b0; long double a0, a1;
  b=m-1; t=(b+m-1)%m; l=b; r=(b+1)%m;
  while(up(H[b],H[(b+1)%m],H[t],H[(t+m-1)%m])) { t=(t+m-1)%m; }
  while(0<=lr(H[b],H[(b+1)%m],H[l],H[(l+m-1)%m])) { l=(l+m-1)%m; }
  while(0 >lr(H[b],H[(b+1)%m],H[r],H[(r+1)%m])) { r=(r+1)%m; }
  // cout << r << ' ' << b << ' ' << (b+1)%m << ' ' << l << ' ' << t << endl;
  a0 = computeArea(H[r],H[(b+1)%m],H[b],H[l],H[t]);
  for (b0=b, b=(b0+m-1)%m;  (b != b0); b=(b+m-1)%m)
  {
    while (up(H[b],H[(b+1)%m],H[t],H[(t+m-1)%m])) { t=(t+m-1)%m; }
    while (0<=lr(H[b],H[(b+1)%m],H[l],H[(l+m-1)%m])) { l=(l+m-1)%m; }
    while (0 >lr(H[b],H[(b+1)%m],H[r],H[(r+m-1)%m])) { r=(r+m-1)%m; }
    // cout << r << ' ' << b << ' ' << (b+1)%m << ' ' << l << ' ' << t << endl;
    a1 = computeArea(H[r],H[(b+1)%m],H[b],H[l],H[t]);
    if ( a0>a1 ) { a0 = a1; }
  }
  return a0;
}

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
  {
    ld a = wrap(H,m);
    os.setf(ios::fixed,ios::floatfield);
    os.precision(2);
    os<<a<<endl;
  }
  return 0;
}