Cod sursa(job #2367301)

Utilizator patcasrarespatcas rares danut patcasrares Data 5 martie 2019 10:00:17
Problema Rubarba Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.91 kb
#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
ifstream fin("rubarba.in");
ofstream fout("rubarba.out");
const long double pi=acos(-1),eps=1e-16;
const int DN=1e5+5;
int n;
long double st,dr,mij1,mij2;
pair<int,int >a[DN];
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()
{
	fin>>n;
	for(int i=1;i<=n;i++)
		fin>>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;
	fout<<fixed<<setprecision(2)<<solve(st);
}