Cod sursa(job #3031342)

Utilizator andrei_marciucMarciuc Andrei andrei_marciuc Data 19 martie 2023 16:12:17
Problema Rubarba Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.48 kb
#include <algorithm>
#include <fstream>
#include <iomanip> 
#include <vector>
#include <cmath>
#include <map>
using namespace std;
 
ifstream cin( "rubarba.in" );
ofstream cout( "rubarba.out" );

typedef pair<double, double> Point;
 
struct Line {
  	double a, b, c;

  	void operator*=( const int& x ) {
		a *= x;
		b *= x;
		c *= x;
  	}
};
 
#define EPS -1e-8

static inline double dist( const Point& p, const Line& l ) {
  	return ( l.a * p.first + l.b * p.second + l.c );
}
 
static inline long double distL( const Point& p, const Line& l ) {
  	return (long double)abs( dist( p, l ) ) / sqrt( l.a * l.a + l.b * l.b );
}
 
static inline Line perpLiniuta( const Line& l, const Point& Left, const Point& Right ) {
  	return { -l.b, l.a, 0 };
}

static inline long double distPLP( const Point& p1, const Point& p2, const Line& l ) {
  	return (long double)abs( dist( p1, l ) - dist( p2, l ) ) / sqrt( l.a * l.a + l.b * l.b );
}

static inline Line liniuta( const Point& p1, const Point& p2 ) {
  	return { -( p2.second - p1.second ), ( p2.first - p1.first ), p1.first * p2.second - p1.second * p2.first };
}
 
map<Point, bool> mp;
vector<Point> point;
int top, Left, Right;
double rez, R;
double x, y;
int n;

static inline bool good( const Point& a, Point b, Point c ) {
  	b = { b.first - a.first, b.second - a.second };
  	c = { c.first - a.first, c.second - a.second };
  	return ( b.first * c.second - b.second * c.first ) >= 0;
}

static inline vector<Point> convexHull( vector<Point>& point ) {
  	vector<Point> hull;
  	sort( point.begin(), point.end() );
  	for( int no = 0; no < 2; no++ ) {
		vector<Point> st;
		for( auto& i : point ) {
	  		if( no == 1 )
				i.second = -i.second;
	  		while( st.size() > 1 && good( st.end()[ -2 ], st.end()[ -1 ], i ) )
				st.pop_back();
	  		st.push_back( i );
		}

		if( no == 1 ) {
	  		st.pop_back();
	  		reverse( st.begin(), st.end() );
	  		st.pop_back();

	  		for( auto& i : st )
				i.second = -i.second;
		}
		hull.insert( hull.end(), st.begin(), st.end() );
  	}
  	return hull;
}

int main() 
{ 
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

  	cin >> n;
  	while( n-- ) {
		cin >> x >> y;
		if( !mp[ { x, y } ] ) {
	  		point.emplace_back( x, y );
	  		mp[ { x, y } ] = true;
		}
  	}
  
  	vector<Point> hull = convexHull( point );

  	Point a = hull[ 0 ];
  	Point b = hull[ 1 ];
  	Line l = liniuta( a, b );
  	Line perp = perpLiniuta( l, a, b );
  
  	for( int i = 0; i < hull.size(); i++ ) {
		if( distL( hull[ i ], l ) >= distL( hull[ top ], l ) + EPS )
	  		top = i;
		if( dist( hull[ i ], perp ) <= dist( hull[ Left ], perp ) - EPS )
	  		Left = i;
		if( dist( hull[ i ], perp ) >= dist( hull[ Right ], perp ) + EPS )
	  		Right = i;
  	}


  	rez = distL( hull[ top ], l ) * distPLP( hull[ Left ], hull[ Right ], perp );
  	for( int i = 1; i < hull.size(); i++ ) {
		a = hull[ i ];
		b = hull[ ( i + 1 ) % hull.size() ];

		l = liniuta( a, b );
		perp = perpLiniuta( l, a, b );

		while( distL( hull[ ( top + 1 ) % hull.size() ], l ) >= distL( hull[ top ], l ) + EPS )
	  		top = ( top + 1 ) % hull.size();

		while( dist( hull[ ( Left + 1 ) % hull.size()], perp ) <= dist( hull[ Left ], perp ) - EPS )
	  		Left = ( Left + 1 ) % hull.size();

		while( dist( hull[ ( Right + 1 ) % hull.size() ], perp ) >= dist( hull[ Right ], perp ) + EPS )
	  		Right = ( Right + 1 ) % hull.size();
	
		if( rez >= ( R = distL( hull[ top ], l ) * distPLP( hull[ Left ], hull[ Right ], perp ) ) + EPS )
	  		rez = R;
  	}
  
  	cout << fixed << setprecision( 2 );
  	cout << rez << '\n';
  	return 0;
}