Cod sursa(job #942476)

Utilizator manciu_ionIon Manciu manciu_ion Data 22 aprilie 2013 18:54:28
Problema Rubarba Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 7.79 kb
#include<fstream>
#include<algorithm>
#include<cmath>

#define x first
#define y second
#define REG register int

using namespace std;

const char iname[]="rubarba.in";
const char oname[]="rubarba.out";
const int maxn=1000003;

ifstream f(iname);
ofstream g(oname);

typedef pair<int,int> point;

point a[maxn];

int n,step,h[maxn*2],been[maxn],maxd,maxl,maxr;

long long area(point a,point b,point c)
{
    long areax=1LL*a.x*(b.y-c.y)+1LL*b.x*(c.y-a.y)+1LL*c.x*(a.y-b.y);
    return areax;
}

long long mod( long  long a)
{
    if(a<0)
        return -a;
    return a;
}

long long dep(point a,point b,point c)
{
    long long depx =  -1LL*(a.x-b.x)*(a.x-b.x)-1LL*(a.y-b.y)*(a.y-b.y)-1LL*(b.x-c.x)*(b.x-c.x)-1LL*(b.y-c.y)*(b.y-c.y)+1LL*(c.x-a.x)*(c.x-a.x)+1LL*(c.y-a.y)*(c.y-a.y);
    return depx;
}

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

bool fcomp(point a,point b)
{
    if(a.y!=b.y)
        return a.y<b.y;
    return a.x<b.x;
}

double minarea=1e26,areax;

int main()
{
    REG i, j, k;
    f>>n;
    if(n<=2)
    {
        g<<"0.0\n";
        f.close();
        g.close();

        return 0;
    }
    for(i=1;i<=n;++i)
        f>>a[i].x>>a[i].y;
    //for(i=1;i<=n;++i)
        //f>>a[i].y;
    sort(a+1,a+n+1,fcomp);
    step=1;
    h[0]=1;
    h[1]=2;
    k=1;
    been[2]=1;
    i=3;
    while(been[1]==0)
    {
        while(been[i])
        {
            i+=step;
            if(i==n)
                step=-1;
        }
        while(k&&(area(a[h[k-1]],a[h[k]],a[i])<0||(area(a[h[k-1]],a[h[k]],a[i])==0&&dis(a[h[k-1]],a[i])>dis(a[h[k-1]],a[h[k]]))))
            been[h[k--]]=0;
        been[h[++k]=i]=1;
    }
    if(a[1]==a[n])
    {
        g<<"0.0\n";
        f.close();
        g.close();

        return 0;
    }
    if(k==1)
        h[++k]=n;
    for(i=1;i<=k;++i)
        h[i+k]=h[i];

    for(i=0;i<k;++i)
    {
        maxd=maxr=maxl=0;
        for(step=1;step<k;step<<=1);
        for(j=i+1;step;step>>=1)
            if(j+step<i+k&&area(a[h[i]],a[h[i+1]],a[h[j+step]])>=area(a[h[i]],a[h[i+1]],a[h[j+step-1]]))
                j+=step;
        maxd=j;
        for(step=1;step<k;step<<=1);
        for(j=i+1;step;step>>=1)
            if(j+step<=maxd&&dep(a[h[i]],a[h[i+1]],a[h[j+step]])>=dep(a[h[i]],a[h[i+1]],a[h[j+step-1]]))
                j+=step;
        maxr=j;
        for(step=1;step<k;step<<=1);
        for(j=maxd;step;step>>=1)
            if(j+step<=i+k&&dep(a[h[i+1]],a[h[i]],a[h[j+step]])>=dep(a[h[i+1]],a[h[i]],a[h[j+step-1]]))
                j+=step;
        maxl=j;
        areax=dep(a[h[i]],a[h[i+1]],a[h[maxr]])+dep(a[h[i+1]],a[h[i]],a[h[maxl]]);
        areax/=2.0*dis(a[h[i]],a[h[i+1]]);
        areax+=dis(a[h[i]],a[h[i+1]]);
        areax*=(1.0*area(a[h[i]],a[h[i+1]],a[h[maxd]]))/dis(a[h[i]],a[h[i+1]]);
        if(areax<minarea)
            minarea=areax;
    }

    g.setf(ios::fixed,ios::floatfield);
    g.precision(2);
    g<<minarea<<"\n";

    f.close();
    g.close();

    return 0;
}

/*
#include <stdio.h>
#include <math.h>

#define NMAX 10000 + 1
#define REG register int

void read();
void write();

void rezolva();
void convex();
double dist(int x1, int y1, int x2,int y2);
void dinamic(double x[], double sm[], int fm[], int pozi, int pozs);
void qsort(int l, int r);

// Variabile globale
double smax = -1, smax1 = -1, smax2 = -1;
int n, k, vs; // vs=varf stiva
int x[NMAX+1];
int y[NMAX+1];
int d[NMAX+1];
int dd[NMAX+1];
int xs[NMAX+1]; // sortate
int ys[NMAX+1];
int os[NMAX+1];
int xc[NMAX+1]; // in convex
int yc[NMAX+1];
int oc[NMAX+1];
int liber[NMAX+1];
int st[NMAX+1]; // stiva pentru convex
int fm1[NMAX+1]; // folosit in sm1(1..n-1)
int fm2[NMAX+1]; // folosit in sm2(2..n)
double dc[NMAX+1];
double a[NMAX+1];
double sm1[NMAX+1];
double sm2[NMAX+1];
long smaxi ,smaxf;



int main()
{
    freopen("mosia.in", "rt", stdin);
    freopen("mosia.out", "wt", stdout);

    read();
     int i;
     for (i = 1; i <= n; ++i) os[i] = i; // inainte de sortare !!!
     qsort(1,n); // ordonez punctele dupa: 1. y=crescator; 2. x=crescator;
     convex();
     for (i = 2; i <= n-1; ++i) dc[i] = dist(xc[i-1], yc[i-1], xc[i+1], yc[i+1]);
     dc[1] = dist(xc[n], yc[n], xc[2], yc[2]);
     dc[n] = dist(xc[n-1], yc[n-1], xc[1], yc[1]);
     for (i = 1; i <= n; ++i) dd[i] = d[oc[i]];
     for (i = 1; i <= n; i++) a[i] = dc[i] * dd[i] / 2.0;
     dinamic(a, sm1, fm1, 1, n-1);
     dinamic(a, sm2, fm2, 2, n);
     smax1 = sm1[n-1];
     if ( !fm1[1] && !fm1[n-1] ) smax1 += x[n];
     smax2 = sm2[n];
     if( !fm2[2] && ! fm2[n] ) smax2 += x[1];
     if (smax1 > smax2) smax = smax1;
     else smax = smax2;
     smaxi = (long)(smax + 0.0000001);
     smaxf = (long)(((smax + 0.0000001) - smaxi) * 1000000);

     write();
}

void read()
 {

     int i;

     scanf("%d", &n);

     for (i = 1; i <= n; ++i)
     {
	     scanf("%d ", &x[i]);
     }


     for (i = 1; i <= n; ++i)
     {
	     scanf("%d ", &y[i]);
     }

     scanf("\n");
 }

void write()
{
    printf("%li.%.6li", smaxi, smaxf);
}

void qsort(REG l, REG r)
{
  REG i, j, mx, my, aux;
  i = l; j = r;
  my = y[(l + r) >> 1];
  mx = x[(l + r)  >> 1];
  do
   { while((y[i] < my) || ((y[i] == my) && (x[i] < mx))) ++i;
     while((y[j] > my) || ((y[j] == my) && (x[j] > mx))) --j;
     if (i <= j)
       { aux = x[i]; x[i] = x[j]; x[j] = aux;
	     aux = y[i]; y[i] = y[j]; y[j] = aux;
	     aux = os[i]; os[i] = os[j]; os[j] = aux;
	     ++i; --j;
       }
    } while(i <= j);
   if (l < j) qsort(l, j);
   if (i < r) qsort(i, r);
}// qsort()

int orient(int x1, int y1, int x2, int y2, int x3, int y3)
{
 // modul(z3/2)=aria_triunghiului !!!
 long z1 = x1 * y2 + x2 * y3 + x3 * y1, z2 = y1 * x2 + y2 * x3 + y3 * x1, z3=z1-z2;
 int sens;
 if (z3 < 0) sens = -1; // sens ace ceasornic
 else if (z3 > 0) sens = 1; // sens trigonometric
      else sens = 0; // coliniare
 return sens;
}// orient(...)

void dinamic(double *x, double *sm, int *fm, int pozi, int pozs)
{ int i;
  for (i = pozi; i <= pozs; ++i) fm[i] = 0;
  sm[pozi] = x[pozi];
  fm[pozi] = 1;
  if (x[pozi+1] > x[pozi])
     {
       sm[pozi+1] = x[pozi+1];
       fm[pozi+1] = 1;
     }
  else sm[pozi+1] = x[pozi];
  for (i = pozi + 2; i <= pozs; ++i)
    if (sm[i-2] + x[i] > sm[i-1])
       {
	     sm[i] = sm[i-2] + x[i];
	     fm[i] = 1;
       }
    else sm[i] = sm[i-1];
}// dinamic(...)

double dist(int x1, int y1, int x2, int y2)
{
  double r1, r2, r3;
  r1 = (double) (x2 - x1) * (x2 - x1);
  r2 = (double) (y2 - y1) * (y2 - y1);
  r3 = sqrt(r1 + r2);
 return r3;
}// dist(...)

void convex() // pune in stiva punctele poligonului convex
{
 int i;
 for (i = 1; i <= n; ++i) liber[i] = 1; // i nu este in infasuratoare
 st[1] = 1;
 st[2] = 2;
 liber[1] = 0;
 liber[2] = 0;
 vs = 2;
 for (i = 3; i <= n; ++i) // agat i la infasuratoare (pe dreapta)
    {
      while (orient(x[st[vs-1]], y[st[vs-1]],x[st[vs]], y[st[vs]],x[i],y[i])==-1) // invers trigonometric
      {
		   liber[st[vs]]=1;
		   --vs;
      }
     ++vs;
     st[vs] = i;
     liber[i] = 0;
    } // n este sigur agatat la infasuratoare si este in stiva
  for (i = n-1; i >= 1; --i) // agat nodul i la infasuratoare (pe stanga)
    if (liber[i])
       { while (orient(x[st[vs-1]],y[st[vs-1]],x[st[vs]],y[st[vs]],x[i],y[i])==-1) // invers trigonometric
	     {
		      liber[st[vs]]=1;
		       --vs;
	     }
	    ++vs;
	    st[vs] = i;
	    liber[i] = 0;
       } // 1 este sigur agatat la infasuratoare si este in stiva
// 1 este si primul si ultimul in stiva !!!
   for (i = 1; i <= vs; ++i)
       {
	     xc[i] = x[st[i]];
	     yc[i] = y[st[i]];
	     oc[i] = os[st[i]];
       }
}// convex
*/