Pagini recente » Cod sursa (job #2732786) | Cod sursa (job #2297784) | Cod sursa (job #1825354) | Cod sursa (job #1030454) | Cod sursa (job #709555)
Cod sursa(job #709555)
#include <stdio.h>
#include <math.h>
#define FI fopen("rubarba.in","r")
#define FO fopen("rubarba.out","w")
template <class T> T abs(T a) { if(a<0) return -a; return a; }
struct Punct {
long x,y;
double dist(Punct p) {
return sqrt((x-p.x)*(x-p.x)+(y-p.y)*(y-p.y));
}
} stiva[100001],punct[100000];
struct Dreapta {
double a,b,c;
double dist(Punct p) {
return abs(a*p.x + b*p.y + c)/sqrt(a*a+b*b);
}
};
long n,stivaSize;
double sol;
void citeste (FILE *f) {
long i;
fscanf(f,"%li",&n);
for(i=0;i<n;i++)
fscanf(f,"%li%li",&punct[i].x,&punct[i].y);
}
int compara(Punct a,Punct b) {
if(a.x<b.x)
return 1;
if(a.x>b.x)
return 0;
if(a.y<b.y)
return 1;
return 0;
}
void schimba(Punct &a, Punct &b) {
Punct aux=a;a=b;b=aux;
}
void sort(long li,long ls) {
long i,j;
if(li>=ls) return;
for(i=j=li+1;i<=ls;i++)
if(compara(punct[i],punct[li]))
schimba(punct[i],punct[j++]);
schimba(punct[li],punct[j-1]);
sort(li,j-2);
sort(j,ls);
}
long produs(Punct a,Punct b,Punct c) {
return a.x*(b.y-c.y)+b.x*(c.y-a.y)+c.x*(a.y-b.y);
}
void infasuratoare() {
int i;
stiva[0]=punct[0];
stiva[1]=punct[1];
stivaSize=2;
for(i=2;i<n;i++)
if(produs(stiva[stivaSize-2],stiva[stivaSize-1],punct[i])>=0) {
stiva[stivaSize]=punct[i];
stivaSize++;
}
else {
stiva[stivaSize-1]=punct[i];
while(stivaSize>2 && produs(stiva[stivaSize-3],stiva[stivaSize-2],stiva[stivaSize-1])<0) {
stivaSize--;
stiva[stivaSize-1]=stiva[stivaSize];
}
}
for(i=n-2;i>=0;i--)
if(produs(stiva[stivaSize-2],stiva[stivaSize-1],punct[i])>=0) {
stiva[stivaSize]=punct[i];
stivaSize++;
}
else {
stiva[stivaSize-1]=punct[i];
while(stivaSize>2 && produs(stiva[stivaSize-3],stiva[stivaSize-2],stiva[stivaSize-1])<0) {
stivaSize--;
stiva[stivaSize-1]=stiva[stivaSize];
}
}
stivaSize--;
}
long stivaVal(long val) {
return val%stivaSize;
}
void rez() {
long i,j,st,dr;
double jDist,stDist,drDist,aux,k,arie,x,y;
i=j=0;
dr=1;
st=-1;
Dreapta d1,d2;
for(;i<stivaSize;i++) {
d1.a=stiva[stivaVal(i)].y-stiva[stivaVal(i+1)].y;
d1.b=stiva[stivaVal(i+1)].x-stiva[stivaVal(i)].x;
d1.c=stiva[stivaVal(i)].x*stiva[stivaVal(i+1)].y - stiva[stivaVal(i)].y*stiva[stivaVal(i+1)].x;
jDist=d1.dist(stiva[stivaVal(j)]);
aux=d1.dist(stiva[stivaVal(j+1)]);
for(;jDist<=aux;j++) {
jDist=aux;
aux=d1.dist(stiva[stivaVal(j+2)]);
}
//k=(double)(stiva[stivaVal(j)].dist(stiva[stivaVal(i)]))/stiva[stivaVal(j)].dist(stiva[stivaVal(i+1)]);
//x=(1/(1+k))*stiva[stivaVal(i)].x+(k/(1+k))*stiva[stivaVal(i+1)].x;
//y=(1/(1+k))*stiva[stivaVal(i)].y+(k/(1+k))*stiva[stivaVal(i+1)].y;
d2.a=-d1.b;
d2.b=d1.a;
d2.c=-d2.a*stiva[stivaVal(j)].x-d2.b*stiva[stivaVal(j)].y;
drDist=d2.dist(stiva[stivaVal(dr)]);
aux=d2.dist(stiva[stivaVal(dr+1)]);
for(;drDist<=aux && dr<=j;dr++) {
drDist=aux;
aux=d2.dist(stiva[stivaVal(dr+2)]);
}
if(st==-1)
st=j+1;
stDist=d2.dist(stiva[stivaVal(st)]);
aux=d2.dist(stiva[stivaVal(st+1)]);
for(;stDist<=aux && st<=i+stivaSize;st++) {
stDist=aux;
aux=d2.dist(stiva[stivaVal(st+2)]);
}
arie=jDist*(stDist+drDist);
if(arie<sol)
sol=arie;
}
}
int main() {
citeste(FI);
if(n<=2) {
fprintf(FO,"0.00");
return 0;
}
sort(0,n-1);
infasuratoare();
sol=1000000;
sol*=sol;
sol*=sqrt(2);
rez();
fprintf(FO,"%.2lf",sol);
return 0;
}