Pagini recente » Cod sursa (job #2775653) | Cod sursa (job #1666582) | Cod sursa (job #1280379) | Cod sursa (job #303730) | Cod sursa (job #2765826)
#include <iostream>
#include <string.h>
#include <random>
#include <fstream>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <iomanip>
#include <algorithm>
#include <math.h>
#include <cmath>
#include <vector>
#include <stack>
#include <queue>
#include <bitset>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <complex>
#include <valarray>
//#include <ext/pb_ds/assoc_container.hpp>
//using namespace __gnu_pbds;
using namespace std;
typedef pair<int, int> pii;
typedef pair<int, string> pis;
typedef pair<string, string> pss;
typedef pair<int, char> pic;
typedef pair<pii, int> piii;
typedef pair<double, double> pdd;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef pair<ll, ll> pll;
typedef pair<int, ll> pil;
typedef pair<ull, ull> pull;
typedef complex<double> cd;
//#define max(n, m) ((n>m)?n:m)
//#define min(n, m) ((n<m)?n:m)
#define f first
#define s second
#define input() ios_base::sync_with_stdio(0);cin.tie(0);
ifstream fin("rubarbe.in");
ofstream fout("rubarbe.out");
struct pt
{
ld x, y;
bool operator<(const pt& p1) const
{
if(p1.x == x) return y < p1.y;
return x < p1.x;
}
};
int cp(pt p1, pt p2)
{
return p1.x * p2.y - p1.y * p2.x;
}
int ccw(pt p1, pt p2, pt p3)
{
pt p4 = {p2.x - p1.x, p2.y - p1.y};
pt p5 = {p3.x - p1.x, p3.y - p1.y};
if(cp(p4, p5) > 0) return 1; // ccw
return -1; // cw
}
int n;
ld mxX, mxY, mnX, mnY, sn, cs;
vector<pt> nums;
vector<pt> upper;
vector<pt> lower;
vector<ld> angles;
ld ans(ld ang)
{
mxX = mxY = -2000000000000000000; mnX = mnY = 2000000000000000000;
sn = sin(ang), cs = cos(ang);
for(int i = 0; i < n; i ++)
mxX = max(mxX, nums[i].x*cs - nums[i].y*sn), mnX = min(mnX, nums[i].x*cs - nums[i].y*sn), mxY = max(mxY, nums[i].x*sn + nums[i].y*cs), mnY = min(mnY, nums[i].x*sn + nums[i].y*cs);
ld ret = (mxX-mnX) * (mxY-mnY);
return ret;
}
ld bs(ld l, ld r)
{
ld mid = (l+r)/2;
if(abs(l - r) < 0.0000000003) return l;
if(ans(mid) > ans(mid + 0.0000000001))
return bs(mid+0.0000000001, r);
return bs(l, mid);
}
int main()
{
fin >> n;
nums.resize(n);
for(int i = 0; i < n; i ++)
fin >> nums[i].x >> nums[i].y;
sort(nums.begin(), nums.end());
for(int i = 0; i < n; i ++)
{
while(upper.size() >= 2 && ccw(upper[upper.size() - 2], upper.back(), nums[i]) == 1)
upper.pop_back();
upper.push_back(nums[i]);
}
for(int i = n-1; i >= 0; i --)
{
while(lower.size() >= 2 && ccw(lower[lower.size() - 2], lower.back(), nums[i]) == 1)
lower.pop_back();
lower.push_back(nums[i]);
}
for(int i = 0; i < upper.size()-1; i ++)
angles.push_back(atan((ld)(upper[i+1].y - upper[i].y))/(ld)(upper[i+1].x - upper[i].x));
for(int i = 0; i < lower.size()-1; i ++)
angles.push_back(atan((ld)(lower[i+1].y - lower[i].y))/(ld)(lower[i+1].x - lower[i].x));
for(int i = 0; i < angles.size(); i ++)
if(angles[i] < 0)
angles[i] += M_PI;
sort(angles.begin(), angles.end());
fout << fixed << setprecision(2) << ans(bs(0, M_PI)) << "\n";
return 1;
}