Pagini recente » Cod sursa (job #1738327) | Istoria paginii runda/simulare_oni2008_clasa10_ziua2 | Cod sursa (job #954056) | Cod sursa (job #2023932) | Cod sursa (job #1135091)
#include <fstream>
#include <cmath>
#include <iomanip>
#include <algorithm>
using namespace std;
ifstream fin ("rubarba.in");
ofstream fout ("rubarba.out");
struct point
{
long double x,y;
}v[100001],s[100001];
int n,k;
long double a,b,c,maxd,area=1e18;
long double det (point a, point b, point c)
{
return (b.x-a.x)*(c.y-a.y) - (c.x-a.x)*(b.y-a.y);
}
bool cmp (point a, point b)
{
return det (v[1],a,b) > 0;
}
long double line_dist (point P)
{
return fabs(a*P.x + b*P.y + c)/sqrt(a*a + b*b);
}
long double line_dist_short (point P)
{
return fabs(a*P.x + b*P.y + c);
}
int bs (int lo, int hi)
{
if (hi < lo)
return 0;
int f = lo, l = hi, mid;
long double val;
while (1)
{
mid = (lo + hi)/2;
long double Lval,Rval;
val = line_dist_short (s[mid]);
if (mid != f)
Lval = line_dist_short (s[mid-1]);
if (mid != l)
Rval = line_dist_short (s[mid+1]);
if ((mid == f || Lval <= val) && (mid == l || val >= Rval))
break;
if (mid > f && Lval > val)
hi = mid-1;
else lo = mid+1;
}
return mid;
}
int main()
{
fin>>n;
int mini = 1;
for (int i=1; i<=n; ++i)
{
fin>>v[i].x>>v[i].y;
if (v[i].x < v[mini].x || (v[i].x == v[mini].x && v[i].y < v[mini].y))
mini = i;
}
swap (v[1],v[mini]);
sort (v+2,v+n+1,cmp);
k = 0;
for (int i=1; i<=n; ++i)
{
while (k >= 2 && det (s[k-1],s[k],v[i]) <= 0)
--k;
s[++k] = v[i];
}
for (int i=1; i<k; ++i)
{
// dreapta care trece prin s[i] si s[i+1]
a = s[i+1].y - s[i].y;
b = s[i].x - s[i+1].x;
c = 1LL*s[i].y*s[i+1].x - 1LL*s[i].x*s[i+1].y;
int wh1 = bs (1,i);
long double d1 = line_dist (s[wh1]);
int wh2 = bs (i+1,k);
long double d2 = line_dist (s[wh2]);
int wh;
if (d1 > d2)
wh = wh1;
else wh = wh2;
//schimbam dreapta la una perpendiculara pe s[i] s[i+1]
if (a != 0)
{
long double m = b/a;
a = m;
b = -1;
c = -m*s[wh].x + s[wh].y;
}
else
{
a = 1;
b = 0;
c = -s[wh].x;
}
if (d1 > d2)
{
int l = bs (wh1,i);
int r1 = bs (1,wh1);
int r2 = bs (i+1,k);
long double dd = max (line_dist(s[r1]),line_dist(s[r2])) + line_dist(s[l]);
area = min (area,d1*dd);
}
else
{
int r = bs (i+1,wh2);
int l1 = bs (1,i);
int l2 = bs (wh2,k);
long double dd = max (line_dist(s[l1]),line_dist(s[l2])) + line_dist(s[r]);
area = min (area,d2*dd);
}
}
//Perechea de puncte (1,k)
a = s[k].y - s[1].y;
b = s[1].x - s[k].x;
c = 1LL*s[1].y*s[k].x - 1LL*s[1].x*s[k].y;
int wh = bs (1,k);
long double d = line_dist (s[wh]);
if (a != 0)
{
double m = b/a;
a = m;
b = -1;
c = -m*s[wh].x + s[wh].y;
}
else
{
a = 1;
b = 0;
c = -s[wh].x;
}
int l = bs (1,wh);
int r = bs (wh,k);
long double dd = line_dist(s[l]) + line_dist(s[r]);
area = min (area,d*dd);
fout<<fixed<<setprecision (2)<<area;
}