Cod sursa(job #3302649)

Utilizator Ilie_MityIlie Dumitru Ilie_Mity Data 9 iulie 2025 19:28:45
Problema Rubarba Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.95 kb
// Ilie "The-Winner" Dumitru
// Dumnezeu sa o ierte
#include<bits/stdc++.h>
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
using ll=long long;
constexpr int NMAX=64;
constexpr ll MOD=1000000009;

using dbl=long double; using pct=std::complex<dbl>;
#define x real
#define y imag
const double PI=4.0*atanl(1.0); const double EPS=1e-9;
// Good eps for long double is ~1e-11
namespace std { bool operator<(pct a, pct b) {
		return std::make_pair(a.x(), a.y()) <
			std::make_pair(b.x(), b.y()); } }
int sgn(dbl d) { return (d>EPS)-(d<-EPS); }
dbl dot(pct a, pct b) { return a.x()*b.x()+a.y()*b.y(); }
dbl cross(pct a, pct b) { return a.x()*b.y()-a.y()*b.x(); }
dbl det(pct a, pct b, pct c) {return cross(b-a, c-a);}
dbl dist(pct a, pct b) { return abs(b-a); }
pct perp(pct a) /* +90deg */ { return {-a.y(), a.x()}; }
pct rotate_ccw(pct a, dbl theta) {
	return a*std::polar((dbl)1.0, theta); }
int half(pct p) { return p<0; }
// std::abs(v) is norm (length) of vector v
// std::norm(v) is square of abs(v)
// std::arg(v) is angle of vector v
// det(a, b, c) is twice the signed area of the triangle abc
// and is >0 iff c is to the left as viewed from a towards b.
// std::polar(r, theta) gets a vector from abs() and arg()
void ExampleUsage() {
	pct a{1.0, 1.0}, b{2.0, 3.0};
	std::cerr<<a<<" "<<b<<std::endl;
	std::cerr<<"Length of ab is: "<<dist(a, b)<<std::endl;
	std::cerr<<"Angle of a is: "<<std::arg(a)<<std::endl;
	std::cerr<<"axb is: "<<cross(a, b)<<std::endl;
	std::cerr<<"Len^2(a) is: "<<std::norm(a)<<std::endl; }





std::vector<pct> HullHalf(std::vector<pct>& P, int z) {
  std::vector<pct> ret; // z = +1 lower, -1 upper ---^
  for(auto p : P) { while(sz(ret)>=2 &&      // (*)
        z*sgn(det(ret.end()[-2], ret.back(), p)) < 0)
      ret.pop_back();
    ret.push_back(p); } return ret; }
std::vector<pct> Hull(std::vector<pct> P) {
  std::sort(all(P)); P.erase(std::unique(all(P)), P.end());
  if(sz(P)<2) return P;
  auto l=HullHalf(P, +1), u=HullHalf(P, -1);
  l.insert(l.end(), u.rbegin()+1, u.rend()-1); return l; }


int N;
std::vector<pct> v;

dbl findArea()
{
	int i, j, k, l;
	dbl ans=1e13;

	for(i=j=k=l=0;i<N;++i)
	{
		pct p=v[(i+1)%N]-v[i];
		p/=std::abs(p);

		while(dot(v[(j+1)%N]-v[j], p)>=0)
			j=(j+1)%N;
		while(cross(v[(k+1)%N]-v[k], p)<=0)
			k=(k+1)%N;
		while(dot(v[l], p) > dot(v[(l+N-1)%N], p))
			l=(l+N-1)%N;
		while(dot(v[(l+1)%N], p) < dot(v[l], p))
			l=(l+1)%N;

		printf("(%.0Lf, %.0Lf)-(%.0Lf, %.0Lf) (%.0Lf, %.0Lf) (%.0Lf, %.0Lf) (%.0Lf, %.0Lf)\n", v[i].x(), v[i].y(), v[(i+1)%N].x(), v[(i+1)%N].y(), v[j].x(), v[j].y(), v[k].x(), v[k].y(), v[l].x(), v[l].y());

		ans=std::min(ans, dot(v[j]-v[l], p)*dot(v[k]-v[i], perp(p)));
	}

	return ans;
}

int main()
{
	FILE* f=fopen("rubarba.in", "r"), *g=fopen("rubarba.out", "w");
	int i, x, y;

	fscanf(f, "%d", &N);
	for(i=0;i<N;++i)
	{
		fscanf(f, "%d%d", &x, &y);
		v.emplace_back(x, y);
	}

	v=Hull(v);
	N=sz(v);

	dbl ans=findArea();
	fprintf(g, "%.2Lf\n", ans);

	fclose(f);
	fclose(g);
	return 0;
}