Pagini recente » Cod sursa (job #813954) | Cod sursa (job #2492818) | Cod sursa (job #956080) | Cod sursa (job #2768314) | Cod sursa (job #1445057)
#include <fstream>
#include <iomanip>
#include <limits>
#include <vector>
#include <utility>
#include <cmath>
using namespace std;
constexpr double inf = numeric_limits<double>::max(),
minus_inf = numeric_limits<double>::lowest();
double get_arie_for_unghi(const double t, const vector<pair<int, int> >& v){
const double cost = cos(t), sint = sin(t);
double minx = inf, miny = inf, maxx = minus_inf, maxy = minus_inf;
double xrotit, yrotit;
for(const auto p : v){
xrotit = p.first * cost - p.second * sint;
yrotit = p.first * sint + p.second * cost;
minx = min(minx, xrotit);
maxx = max(maxx, xrotit);
miny = min(miny, yrotit);
maxy = max(maxy, yrotit); }
return (maxx-minx) * (maxy-miny); }
double ternary_search(const vector<pair<int, int> >& v, const double s = 0, const double d = M_PI_2){
if(d-s < 1e-14){
return s; /* ~= d*/; }
else{
const double delta = (d-s)/3.0,
m1 = s + delta, m2 = d - delta,
val1 = get_arie_for_unghi(m1, v),
val2 = get_arie_for_unghi(m2, v);
if(val1 < val2){
return ternary_search(v, s, m2); }
else{
return ternary_search(v, m1, d); } } }
void citeste_date(vector<pair<int, int> >& v){
ifstream f("rubarba.in");
int n;
f >> n;
v.resize(n);
for(auto& x : v){
f >> x.first >> x.second; } }
int main(){
vector<pair<int, int> > v;
citeste_date(v);
ofstream g("rubarba.out");
g << fixed << setprecision(2) << get_arie_for_unghi(ternary_search(v), v);
return 0; }