Pagini recente » Cod sursa (job #2174941) | Cod sursa (job #102399) | Cod sursa (job #328166) | Cod sursa (job #2669222) | Cod sursa (job #1350152)
#include <fstream>
#include <cmath>
#include <iomanip>
#include <algorithm>
using namespace std;
ifstream in("rubarba.in");
ofstream out("rubarba.out");
struct point
{
int x,y;
};
const int nmax = 100006;
int n, k;
double a, b, c;
long double area = 1000000000000;
point v[nmax], st[nmax];
double modul(double x)
{
if(x<0)
return -x;
else
return x;
}
long long det (point a, point b, point c)
{
return (long long)(b.x - a.x)*(long long)(c.y - a.y) - (long long)(c.x - a.x) * (long long)(b.y - a.y);
}
bool cmp(point a, point b)
{
return det(v[1], a, b)>0;
}
double dist(point p)
{
return modul(a * p.x + b * p.y + c) / sqrt(a * a + b * b);
}
double line_dist_short(point p)
{
return modul(a*p.x + b*p.y + c);
}
int bs (int lo, int hi)
{
if (hi<lo)
return 0;
int inlo = lo, inhi = hi, mid;
double val;
while (1)
{
mid = (lo + hi)/2;
double lval, rval;
val = line_dist_short (st[mid]);
if (mid!=inlo)
lval = line_dist_short (st[mid - 1]);
if (mid!=inhi)
rval = line_dist_short (st[mid + 1]);
if ((mid==inlo || lval<=val) && (mid==inhi || val>=rval))
break;
if (mid>inlo && lval>val)
hi = mid - 1;
else
lo = mid + 1;
}
return mid;
}
int main()
{
int player_unu=0;
out<<setprecision(2)<<fixed;
in>>n;
int mini = 1;
for(int i = 1; i<=n; i++)
{
in>>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(st[k - 1], st[k], v[i])<=0)
--k;
k++;
st[k] = v[i];
}
for(int i = 1; i<k; i++)
{
a = st[i + 1].y - st[i].y;
b = st[i].x - st[i + 1].x;
c = (long long)st[i].y * (long long)st[i+1].x - (long long)st[i].x*(long long)st[i+1].y;
int dr1 = bs(1, i);
double d1 = dist(st[dr1]);
int dr2 = bs (i + 1, k);
double d2 = dist(st[dr2]);
int dr;
if(d1>d2)
dr = dr1;
else
dr = dr2;
if(a!=0)
{
double m = b / a;
a = m;
b = -1;
c = -m * st[dr].x + st[dr].y;
}
if(d1>d2)
{
int l = bs(dr1, i);
int r1 = bs (1, dr1);
int r2 = bs (i + 1, k);
double chestie = max (dist(st[r1]), dist(st[r2])) + dist(st[l]);
area = min (area,(long double)d1 * chestie);
}
else
{
int r = bs (i + 1, dr2);
int l1 = bs (1, i);
int l2 = bs (dr2, k);
double chestie = max (dist(st[l1]), dist(st[l2])) + dist(st[r]);
area = min (area, (long double)d2 * chestie);
}
}
a = st[k].y - st[1].y;
b = st[1].x - st[k].x;
c = (long long)st[1].y * (long long)st[k].x - (long long)st[1].x * (long long)st[k].y;
int dr = bs (1, k);
double d = dist(st[dr]);
if(a!=0)
{
double m = b / a;
a = m;
b = -1;
c = -m * st[dr].x + st[dr].y;
}
int l = bs (1, dr);
int r = bs (dr, k);
double chestie = dist(st[l]) + dist(st[r]);
area = min(area, (long double)d * chestie);
out<<area;
return player_unu;
}