Pagini recente » Cod sursa (job #1444609) | Cod sursa (job #1301786) | Cod sursa (job #2535519) | Cod sursa (job #1311399) | Cod sursa (job #1277324)
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#define NMAX 100005
#define eps 0.000001
using namespace std;
int n;
struct punct
{
double x,y;
punct(double x=0,double y=0): x(x), y(y) {}
}v[NMAX];
inline double dist(const punct &a,const punct &b){
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
inline double ccw(const punct &a,const punct &b,const punct &c){
return ((a.x-b.x)*(c.y-b.y)-(a.y-b.y)*(c.x-b.x));
}
bool operator<(const punct &a,const punct &b){
double c=ccw(a,v[1],b);
if(fabs(c)<eps)
return (a.x<b.x);
return (c>0);
}
inline void graham_scan(){
int poz=1;
for(int i=2;i<=n;i++)
if(v[i].x<v[poz].x)
poz=i;
else if(v[i].x==v[poz].x)
if(v[i].y<v[poz].y)
poz=i;
swap(v[1],v[poz]);
if(n>1)
sort(v+2,v+n+1);
punct stiva[NMAX];
poz=0;
for(int i=1;i<=n;i++){
while(poz>1 && ccw(stiva[poz-1],stiva[poz],v[i])>=-eps)
poz--;
stiva[++poz]=v[i];
}
for(int i=1;i<=poz;i++)
v[i]=stiva[i];
n=poz;
}
inline double precalc_bounding_box(){
double x_min=v[1].x,y_min=v[1].y;
double x_max=v[1].x,y_max=v[1].y;
for(int i=2;i<=n;i++){
x_min=min(x_min,v[i].x);
y_min=min(y_min,v[i].y);
x_max=max(x_max,v[i].x);
y_max=max(y_max,v[i].y);
}
return (x_max-x_min)*(y_max-y_min);
}
double dist(double m,int i,int j){
double b=dist(v[i],punct(0,v[i].y-m*v[i].x));
double a=ccw(v[j],v[i],punct(0,v[i].y-m*v[i].x));
a/=b;
if(a<0)
a*=(-1);
return a;
}
double dmax(double m){
int p_min=1,p_max=1;
double y1,y2;
for(int i=1;i<=n;i++){
y1=v[i].y-m*v[i].x;
y2=v[p_min].y-m*v[p_min].x;
if(y1<y2)
p_min=i;
y2=v[p_max].y-m*v[p_max].x;
if(y1>y2)
p_max=i;
}
return dist(m,p_min,p_max);
}
ofstream cout("rubarba.out");
inline void calculate(){
double ans=precalc_bounding_box();
double curent;
for(int i=1;i<=n;i++)
if(v[i].x!=v[i%n+1].x && v[i].y!=v[i%n+1].y){
curent=dmax((v[i].y-v[i%n+1].y)/(v[i].x-v[i%n+1].x))*dmax(-(v[i].x-v[i%n+1].x)/(v[i].y-v[i%n+1].y));
if(curent<ans)
ans=curent;
}
cout<<fixed<<setprecision(2)<<ans<<'\n';
}
int main()
{
ifstream cin("rubarba.in");
cin>>n;
for(int i=1;i<=n;i++){
cin>>v[i].x>>v[i].y;
v[i].x++;v[i].y++;
}
graham_scan();
calculate();
cin.close();
cout.close();
return 0;
}