Pagini recente » Cod sursa (job #2964608) | Cod sursa (job #2550694) | Cod sursa (job #2578491) | Cod sursa (job #2568240) | Cod sursa (job #1460591)
// Ideea de baza este ca una din laturile dreptunghiului coincide cu o latura de pe infasuratoare
// Iar celelalte delimitari sunt : cel mai departat punct , cel mai departat din stanga punct , si
// ce mai departat din dreapta punct. Acestea fiind in ordine trigonometrica sau anti, putem folosi
// cautarea binara pentru a le determina , asadar un O(H) pentru fiecare dreapta fixata si
// O(log(H)) pentru gasirea celorlalte trei puncte
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
#define point pair < double , double >
ifstream fin("rubarba.in");
ofstream fout("rubarba.out");
const int NSIZE = 100000 + 10;
point p[NSIZE] , hull[NSIZE];
int sizeHull , N;
double aCoef , bCoef , cCoef;
double cross(point A,point B,point C)
{
double a = A.y - B.y;
double b = B.x - A.x;
double c = A.x * B.y - B.x * A.y;
double product = a * C.x + b * C.y + c;
return product;
}
bool compare(point A,point B)
{
return (cross(p[1] , A , B) > 0);
}
void read()
{
fin >> N;
for (int i = 1 ; i <= N ; ++i)
fin >> p[i].x >> p[i].y;
}
double getDistance(point p)
{
double f = (aCoef * p.x + bCoef * p.y + cCoef) / sqrt(aCoef * aCoef + bCoef * bCoef);
return (f > 0) ? f : -f;
}
double lineDist(point p)
{
double f = aCoef * p.x + bCoef * p.y + cCoef;
return (f > 0) ? f : -f;
}
int binarySearch(int le , int ri)
{
int f = 0 , _le = le , _ri = ri;
if (le > ri) return 0;
while (true)
{
int mid = (le + ri) >> 1;
double crtValue = lineDist(hull[mid]);
double leftValue , rightValue;
if (mid != _le) leftValue = lineDist(hull[mid - 1]);
if (mid != _ri) rightValue = lineDist(hull[mid + 1]);
if ((mid == _le || leftValue <= crtValue) && (mid == _ri || rightValue <= crtValue))
return mid;
(mid > _le && leftValue > crtValue) ? ri = mid - 1 : le = mid + 1;
}
}
void convexHull()
{
int _i = 1;
stack < point > inStack;
for (int i = 1 ; i <= N ; ++i)
if (p[i] < p[1]) swap(p[1] , p[i]);
sort(p + 2 , p + N + 1 , compare);
inStack.push(p[1]);
inStack.push(p[2]);
for (int i = 3 ; i <= N ; ++i)
{
while (inStack.size() >= 2)
{
point prv = inStack.top();
inStack.pop();
point prvv = inStack.top();
if (cross(prvv , prv , p[i]) <= 0) continue;
else
{
inStack.push(prv);
break;
}
}
inStack.push(p[i]);
}
while (inStack.size())
{
hull[++sizeHull] = inStack.top();
inStack.pop();
}
reverse(hull + 1 , hull + sizeHull + 1);
}
void solve()
{
hull[sizeHull + 1] = hull[1];
double answer = 1ll << 60;
for (int i = 1 ; i <= sizeHull ; ++i)
{
aCoef = hull[i + 1].y - hull[i].y;
bCoef = hull[i].x - hull[i + 1].x;
cCoef = hull[i].y * hull[i + 1].x - hull[i].x * hull[i + 1].y;
int _left = binarySearch(1 , i);
int _right = binarySearch(i + 1 , sizeHull);
double leftDistance = getDistance(hull[_left]);
double rightDistance = getDistance(hull[_right]);
int furthest = (leftDistance > rightDistance) ? _left : _right;
if (aCoef != 0)
{
double m = bCoef / aCoef;
aCoef = m;
bCoef = -1;
cCoef = (-1) * m * hull[furthest].x + hull[furthest].y;
}
if (leftDistance > rightDistance)
{
//iau intervalul unde se afla distanta mai mare [1 , i]
//il impart in doua bucati dupa furthest si iau cele mai indepartate din cele doua intervale
int _x = binarySearch(1 , furthest);
int _y = binarySearch(furthest , i);
int _z = binarySearch(i + 1 , sizeHull);
answer = min(answer , leftDistance *
(max(getDistance(hull[_x]) , getDistance(hull[_z])) + getDistance(hull[_y])));
}
else
{
//analog daca e in [i + 1 , sizeHull]
int _x = binarySearch(i + 1 , furthest);
int _y = binarySearch(furthest , sizeHull);
int _z = binarySearch(1 , i);
answer = min(answer , rightDistance *
(max(getDistance(hull[_y]) , getDistance(hull[_z])) + getDistance(hull[_x])));
}
}
fout << fixed << setprecision(2) << answer << '\n';
}
int main()
{
read();
convexHull();
solve();
return 0;
}