Cod sursa(job #1445057)

Utilizator tamionvTamio Vesa Nakajima tamionv Data 30 mai 2015 11:44:25
Problema Rubarba Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.42 kb
#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; }