Cod sursa(job #198929)

Utilizator anna_bozianuBozianu Ana anna_bozianu Data 16 iulie 2008 10:51:05
Problema Rubarba Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.82 kb
#include<stdio.h>
#define N 100001
#define NN 200002
long long n,i,a[N],b[N],amin,bmin,imin,aux,p,u,c[NN],p1,p2,p3,p4,xx[NN],yy[NN];
double sol;
void citire();
void ch();
void sh(long long i1,long long i2);
void hd(long long ic,long long nc);
void solve();
long long ord(long long i1,long long i2,long long i3);
void init();
void get_next();
long ps(long long i1,long long i2);
int main()
{
	freopen("rubarba.out","wt",stdout);
	citire();
	init();
	solve();
	for(i=1;i<u;i++)
	{ get_next();
	  solve();
	}
	printf("%.2lf",sol);
	fcloseall();
	return 0;
}
void ch()
{
    for(i=n/2;i>=1;i--)hd(i,n);
    for(i=n;i>=1;i--){sh(1,i);hd(1,i-1);}
    p=1;u=1;
    c[p]=0;
    for(i=1;i<=n;i++)
    { if(u==1){c[++u]=i;continue;}
      if(ord(c[u-1],c[u],i)==1){c[++u]=i;continue;}
      while(u>1&&ord(c[u-1],c[u],i)==-1)u--;
      c[++u]=i;
    }
}
void sh(long long i1,long long i2)
{
	aux=a[i1];a[i1]=a[i2];a[i2]=aux;
	aux=b[i1];b[i1]=b[i2];b[i2]=aux;
}
void hd(long long ic,long long nc)
{
	long long is,is1;
	is=2*ic;is1=is+1;
	if(is>nc)return;
	if(is<nc) if(ord(0,is,is1)==1)is=is1;
	if(ord(0,ic,is)==1){sh(is,ic);hd(is,nc);}
}
long long ord(long long i1,long long i2,long long i3)
{
	long long d1,d2;
	d1=a[i1]*b[i2]+a[i2]*b[i3]+a[i3]*b[i1];
	d2=b[i1]*a[i2]+b[i2]*a[i3]+b[i3]*a[i1];
	if(d1>d2)return 1;
	if(d1<d2)return -1;
	d1=(a[i1]-a[i2])*(a[i2]-a[i3]);
	if(d1>0)return 1;
	if(d1<0)return -1;
	d2=(b[i1]-b[i2])*(b[i2]-b[i3]);
	if(d2>0)return 1;
	return -1;
}
void init()
{

	for(i=1;i<=u;i++)
	{ xx[i]=a[c[i+1]]-a[c[i]];
	  yy[i]=b[c[i+1]]-b[c[i]];
	}
	for(i=1;i<=u;i++)
	{ c[i+u]=c[i];xx[i+u]=xx[i];yy[i+u]=yy[i];}
	p1=1;
	p2=1;
	while(xx[p1]*xx[p2]+yy[p1]*yy[p2]>0)p2++;
	p3=p2;
	while(xx[p1]*yy[p3]>yy[p1]*xx[p3])p3++;
	p4=p3;
	while(xx[p1]*xx[p4]+yy[p1]*yy[p4]<0)p4++;
	sol=1000001;sol*=sol;
}
void get_next()
{
	p1++;
	while(xx[p1]*xx[p2]+yy[p1]*yy[p2]>0)p2++;
	while(xx[p1]*yy[p3]>yy[p1]*xx[p3])p3++;
	while(xx[p1]*xx[p4]+yy[p1]*yy[p4]<0)p4++;

}
void solve()
{       double a1,a2,a3,a4,a5,b1,b2,b3,b4,b5,aria;
	a1=(double)a[c[p1]];b1=(double)b[c[p1]];
	a2=(double)a[c[p1+1]];b2=(double)b[c[p1+1]];
	a3=(double)a[c[p2]];b3=(double)b[c[p2]];
	a4=(double)a[c[p3]];b4=(double)b[c[p3]];
	a5=(double)a[c[p4]];b5=(double)b[c[p4]];
	//d1:(b2-b1)(x-a1)-(a2-a1)(y-b1)=0;
	//d2:(a2-a1)(x-a3)+(b2-b1)(y-b3)=0;
	aria=(b2-b1)*(a4-a1)-(a2-a1)*(b4-b1);
	aria*=(a2-a1)*(a5-a3)+(b2-b1)*(b5-b3);
	aria/=(a2-a1)*(a2-a1)+(b2-b1)*(b2-b1);
	if(aria<0)aria=-aria;
	if(aria<=sol)sol=aria;
}
void citire()
{
	freopen("rubarba.in","rt",stdin);
	freopen("rubarba.out","wt",stdout);
	scanf("%lld",&n);amin=1000001;bmin=1000001;
	for(i=0;i<n;i++)
	{ scanf("%lld%lld",&a[i],&b[i]);
	  if(a[i]<amin||(a[i]==amin&&b[i]<bmin))
	  { imin=i;amin=a[i];bmin=b[i];}
	}
	sh(imin,0);
	n--;
	ch();
}