Cod sursa(job #2923934)

Utilizator bem.andreiIceman bem.andrei Data 21 septembrie 2022 15:19:03
Problema Rubarba Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.9 kb
#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
ifstream r("rubarba.in");
ofstream w("rubarba.out");

const long double pi=acos(-1),eps=1e-16;
int n;
long double st,dr,mij1,mij2;
pair<int,int >a[100003];
long double rx[2],ry[2],z,k[2];
long double solve(long double val)
{
	k[0]=cos(val);
	k[1]=sin(val);
	rx[0]=ry[0]=1e18;
	rx[1]=ry[1]=-1e18;
	for(int i=1;i<=n;i++)
	{
		z=k[0]*a[i].x+k[1]*a[i].y;
		rx[0]=min(rx[0],z);
		rx[1]=max(rx[1],z);

		z=-k[1]*a[i].x+k[0]*a[i].y;
		ry[0]=min(ry[0],z);
		ry[1]=max(ry[1],z);
	}
	return (rx[1]-rx[0])*(ry[1]-ry[0]);
}
int main()
{
	r>>n;
	for(int i=1;i<=n;i++){
		r>>a[i].x>>a[i].y;
	}
	st=0;
	dr=pi/2;
	while(dr-st>=eps)
	{
		mij1=st+(dr-st)/3;
		mij2=dr-(dr-st)/3;
		if(solve(mij1)<solve(mij2)){
			dr=mij2;
		}
		else{
			st=mij1;
		}
	}
	st=(st+dr)/2;
	w<<fixed<<setprecision(2)<<solve(st);
}