Pagini recente » Cod sursa (job #3286566) | Cod sursa (job #2893999) | Cod sursa (job #3209764) | Cod sursa (job #1758640) | Cod sursa (job #3281126)
#include <fstream>
#include <algorithm>
#include <cmath>
#include <iomanip>
using namespace std;
#define int long long
ifstream in("rubarba.in");
ofstream out("rubarba.out");
int n;
long double ans;
pair<int, int> v[100005];
pair<int, int> s[100005];
pair<long double, long double> w[100005];
int INF = (1LL << 60);
int det(pair<int, int> a, pair<int, int> b, pair<int, int> c)
{
return (b.first - a.first) * (c.second - a.second) - (c.first - a.first) * (b.second - a.second);
}
int dist(pair<int, int> a, pair<int, int> b)
{
return (a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (a.second - b.second);
}
bool cmp(const pair<int, int> &a, const pair<int, int> &b)
{
int d = det(v[1], a, b);
if(d == 0)
{
return dist(v[1], a) < dist(v[1], b);
}
return d < 0;
}
signed main()
{
in>>n;
int poz = 1;
for(int i = 1; i<=n; i++)
{
in>>v[i].first>>v[i].second;
if(v[i] < v[poz])
{
poz = i;
}
}
swap(v[1], v[poz]);
sort(v + 2, v + n + 1, cmp);
s[1] = v[1];
s[2] = v[2];
int head = 2;
for(int i = 3; i<=n; i++)
{
while(head >= 2 && det(s[head - 1], s[head], v[i]) >= 0)
{
head--;
}
head++;
s[head] = v[i];
}
s[head + 1] = s[1];
ans = INF;
for(int i = 1; i<=head; i++)
{
long double unghi = atan2(s[i + 1].second - s[i].second, s[i + 1].first - s[i].first);
unghi = -unghi;
long double xmax = -INF;
long double xmin = INF;
long double ymax = -INF;
long double ymin = INF;
for(int j = 1; j<=head; j++)
{
w[j].first = (long double)s[j].first * cos(unghi) - (long double)s[j].second * sin(unghi);
w[j].second = (long double)s[j].first * sin(unghi) + (long double)s[j].second * cos(unghi);
xmax = max(xmax, w[j].first);
xmin = min(xmin, w[j].first);
ymax = max(ymax, w[j].second);
ymin = min(ymin, w[j].second);
}
long double arie = (long double)(xmax - xmin) * (ymax - ymin);
ans = min(ans, arie);
}
out<<setprecision(2)<<fixed<<ans;
return 0;
}