Cod sursa(job #65716)

Utilizator fireatmyselfBogdan-Alexandru Stoica fireatmyself Data 11 iunie 2007 17:55:19
Problema Rubarba Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.87 kb
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>

#define NMAX 211111
#define Reps 1e-5
#define ueps 1e-10
#define INF 1e15

long double x[NMAX], y[NMAX], R[NMAX], u[NMAX];
long double a, b, c, A, C, t1, t2, pi, xma, xmi, yma, ymi, xx, yy;
long double xmin[2*NMAX], ymin[2*NMAX], xmax[2*NMAX], ymax[2*NMAX];
int pxmin[2*NMAX], pymin[2*NMAX], pxmax[2*NMAX], pymax[2*NMAX];
int stack[NMAX], o[NMAX], oaux[NMAX], inside[NMAX], smn;
int i, j, k, m, N, p, prev, next, i1, i2, i3, i4;

/*
long double dist2d(long double xa, long double ya, long double xb,double yb)
{
return sqrtl((xa-xb)*(xa-xb)+(ya-yb)*(ya-yb));
}
*/

int semn(long double a, long double b, long double c, long double x, long double y)
{
long double r = a*x + b*y + c;

if (r < Reps && r > -Reps) return 0;
else
  if (r>0) return 1;
else
  return -1;
}

void sort(int li, int ls)
{
if (ls-li==1)
  {
  if (x[o[li]]>x[o[ls]] ||
     (x[o[li]]==x[o[ls]] && y[o[li]]>y[o[ls]]))
    {
    p=o[li]; o[li]=o[ls]; o[ls]=p;
    }
  }
else
if (ls-li>1)
  {
  sort(li,(li+ls)>>1);
  sort(((li+ls)>>1)+1,ls);

  k=li-1;
  i=li;
  m=(li+ls)>>1;
  j=m+1;

  while (i<=m && j<=ls)
    {
    k++;

    if (x[o[i]]<x[o[j]] ||
       (x[o[i]]==x[o[j]] && y[o[i]]<y[o[j]]))
      {
      oaux[k]=o[i];
      i++;
      }
    else
      {
      oaux[k]=o[j];
      j++;
      }
    }

  if (i<=m)
    {
    for (j=i;j<=m;j++)
      {
      k++;
      oaux[k]=o[j];
      }
    }
  else
    {
    for (i=j;i<=ls;i++)
      {
      k++;
      oaux[k]=o[i];
      }
    }

  for (k=li;k<=ls;k++)
    o[k]=oaux[k];
  }
}

long double arie(long double t)
{
long double V1, V2, V3, V4;

V1 = R[i2] * cos(u[i2] + t);
V2 = R[i1] * cos(u[i1] + t);
V3 = R[i3] * sin(u[i3] + t);
V4 = R[i4] * sin(u[i4] + t);

return (V1 - V2) *
       (V4 - V3);
}

void zero(void)
{
freopen("rubarba.out", "w", stdout);
printf("0.00\n");
exit(0);
}

int main()
{
    freopen("rubarba.in", "r", stdin);
    
    scanf("%d", &N);
    for (i = 1; i <= N; i++)
    {
        scanf("%Lf %Lf",&x[i],&y[i]);
        o[i]=i;
   }

if (N < 3)
   zero();

sort(1, N);

/* Compute convex hull */
memset(inside, 0, sizeof(inside));
stack[1] = 1; stack[2] = 2; inside[2] = 1; i = 2;

/* Step 1 */
for (p = 3; p <= N; p++)
  {
if (fabs(x[o[p]] - x[o[p-1]]) < Reps &&
		fabs(y[o[p]] - y[o[p-1]]) < Reps)
	{
		inside[p] = 1;
		continue;
	}

  smn = -1;
  while (smn < 0)
    {
    if (i == 1)
      {
      i++;
      stack[i] = p;
      inside[p] = 1;
      smn = 0;
      }
    else
      {
      a=y[o[stack[i-1]]]-y[o[stack[i]]];
      b=x[o[stack[i]]]-x[o[stack[i-1]]];
      c=x[o[stack[i-1]]]*y[o[stack[i]]]-x[o[stack[i]]]*y[o[stack[i-1]]];

      smn=semn(a,b,c,x[o[p]],y[o[p]]);
      if (smn>=0)
      {
      i++;
      stack[i]=p;
      inside[p]=1;
      }
      else
      {
      inside[stack[i]]=0;
      i--;
      }
      }
    }
  }

/* Step 2 */
for (p = N; p >= 1; p--)
  if (!inside[p])
    {
	if (fabs(x[o[p]] - x[o[p+1]]) < Reps &&
		fabs(y[o[p]] - y[o[p+1]]) < Reps &&
		p < N)
	{
		inside[p] = 1;
		continue;
	}

    smn = -1;
    while (smn < 0)
      {
      if (i==1)
      {
      i++;
      stack[i]=p;
      inside[p]=1;
      smn=0;
      }
      else
      {
      a=y[o[stack[i-1]]]-y[o[stack[i]]];
      b=x[o[stack[i]]]-x[o[stack[i-1]]];
      c=x[o[stack[i-1]]]*y[o[stack[i]]]-x[o[stack[i]]]*y[o[stack[i-1]]];

    smn=semn(a,b,c,x[o[p]],y[o[p]]);
    if (smn>=0)
    {
      i++;
        stack[i]=p;
        inside[p]=1;
    }
    else
    {
    inside[stack[i]]=0;
    i--;
    }
  }
}
}

    N = i - 1;

    a = b = 0;
    for (k = 1; k < i; k++)
    {
        a += x[o[stack[k]]];
        b += y[o[stack[k]]];
        R[k] = x[o[stack[k]]];
        u[k] = y[o[stack[k]]];
    }

    a /= N, b /= N;

    for (k = 1; k < i; k++)
    {
        x[k - 1] = R[k]/* - a*/;
        y[k - 1] = u[k]/* - b*/;
        R[k - 1] = sqrt(x[k - 1] * x[k - 1] + y[k - 1] * y[k - 1]);
        u[k - 1] = atan2(y[k - 1], x[k - 1]);
    }

	R[N] = R[0], u[N] = u[0];
	x[N] = x[0]; y[N] = y[0];


    A = INF;

    for (i = 0; i < N; i++)
    {
        b = atan2(y[i+1] - y[i], x[i+1] - x[i]);

        xmi = ymi = INF; xma = yma = -INF;

        for (j = 0; j < N; j++)
        {
            xx = R[j] * cos(u[j] - b);
            yy = R[j] * sin(u[j] - b);

            if (xx < xmi)
               xmi = xx;
            if (xx > xma)
               xma = xx;
            if (yy < ymi)
               ymi = yy;
            if (yy > yma)
               yma = yy;
        }

        if ((xma - xmi)*(yma - ymi) < A)
           A = (xma - xmi)*(yma - ymi);
    }

    freopen("rubarba.out", "w", stdout);
    printf("%.2Lf\n", A);

    return 0;
}