Pagini recente » Cod sursa (job #549651) | Cod sursa (job #2498485) | Cod sursa (job #326772) | Calibrare limite de timp | Cod sursa (job #2832835)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("rubarba.in");
ofstream fout("rubarba.out");
using ld = long double;
const int NMAX(100005);
struct chestie
{
int x, y;
} v[NMAX], st[NMAX];
ld pi = 4 * atan(1);
ld det(chestie a, chestie b, chestie c)
{
return a.x * b.y + a.y * c.x + b.x * c.y - c.x * b.y - a.y * b.x - a.x * c.y;
}
inline bool cmp1(chestie a, chestie b)
{
if(a.y == b.y)
return a.x > b.x;
return a.y < b.y;
}
inline bool cmp2(chestie a, chestie b)
{
return (det(v[1], a, b) > 0.0);
}
pair<ld, ld> convP(ld x, ld y, ld angle, chestie p)
{
ld s = sin(-angle);
ld c = cos(-angle);
ld ax = p.x - x;
ld ay = p.y - y;
ld newX = ax * c - ay * s + x;
ld newY = ax * s + ay * c + y;
return {newX, newY};
}
int main()
{
int n;
fin >> n;
for(int i = 1; i <= n; ++i)
fin >> v[i].x >> v[i].y;
sort(v + 1, v + n + 1, cmp1);
sort(v + 2, v + n + 1, cmp2);
int nr = 2;
st[1] = v[1];
st[2] = v[2];
v[n + 1] = v[1];
for(int i = 3; i <= n + 1; ++i)
{
while(nr > 1 && det(st[nr - 1], st[nr], v[i]) <= 0.0)
--nr;
st[++nr] = v[i];
}
ld minn = 1e9;
///obs: latura paralela cu una de pe infasuratoare
for(int i = 1; i < nr; ++i)
{
chestie a = st[i], b = st[i + 1];
if(a.y > b.y)
swap(a, b);
b.x -= a.x;
b.y -= a.y;
ld ang = atan2(b.y, b.x);
ld minnX = 1e9, minnY = 1e9, maxxX = -1e9, maxxY = -1e9;
for(int j = 1; j <= nr; ++j)
{
pair<ld, ld> newP = convP(a.x, a.y, ang, st[j]);
if(st[j].x == a.x && st[j].y == a.y)
newP = {a.x, a.y};
minnX = min(minnX, newP.first), maxxX = max(maxxX, newP.first);
minnY = min(minnY, newP.second), maxxY = max(maxxY, newP.second);
}
minn = min(minn, abs((maxxX - minnX) * (maxxY - minnY)));
}
fout << fixed << setprecision(3) << minn << '\n';
return 0;
}