Cod sursa(job #2367231)

Utilizator patcasrarespatcas rares danut patcasrares Data 5 martie 2019 09:39:21
Problema Rubarba Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.15 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-4;
const int DN=1e5+5;
int n;
long double st,dr,mij1,mij2;
pair<long double,long double>a[DN];
long double rx[2],ry[2],z,k[2],mi;
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=a[i].x*k[0]+a[i].y*k[1];
		rx[0]=min(rx[0],z);
		rx[1]=max(rx[1],z);

		z=-a[i].x*k[1]+a[i].y*k[0];
		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;
    mi=1e18;
	st=0;
	dr=pi;
	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;
	mi=min(mi,solve(st));

	st=pi;
	dr=2*pi;
	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;
	mi=min(mi,solve(st));
	fout<<fixed<<setprecision(2)<<mi;
}