Cod sursa(job #3363438)

Utilizator Ilie_MityIlie Dumitru Ilie_Mity Data 18 august 2026 00:22:50
Problema Camera Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 4.54 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()
#define err(...) fprintf(stderr, __VA_ARGS__)
using ll=long long;
using dbl=long double;
constexpr int NMAX=2'005;
constexpr ll MOD=1'000'000'007;

using coord=dbl;
constexpr coord EPS=1e-6;

struct pct
{
	coord x, y;
};

struct line
{
	// y=ax+c
	coord a, c;

	coord operator()(coord x) const
	{
		return a*x+c;
	}
};

int N;
pct v[NMAX];
coord minX=-MOD, maxX=MOD;
std::vector<line> up, down;

coord xintersect(line l, line m)
{
	return (m.c-l.c)/(l.a-m.a);
}

int sgn(coord x)
{
	return (x>=EPS)-(x<=-EPS);
}

coord cross(pct p, pct q)
{
	return p.x*q.y-q.x*p.y;
}

coord cross(pct p, pct q, pct r)
{
	return cross({q.x-p.x, q.y-p.y}, {r.x-p.x, r.y-p.y});
}

void init()
{
	int i, min=0;
	for(i=1;i<N;++i)
		if(v[i].x<v[min].x || (v[i].x==v[min].x && v[i].y<v[min].y))
			min=i;
	std::rotate(v, v+min, v+N);
	v[N]=v[0];

	if(sgn(cross(v[N-1], v[0], v[1]))!=sgn(cross({0, 0}, {1, 0}, {1, 1})))
		std::reverse(v, v+N+1);

	for(i=0;i<N;++i)
	{
		if(v[i].x==v[i+1].x)
		{
			if(v[i].y<v[i+1].y)
				maxX=std::min(maxX, v[i].x);
			else
				minX=std::max(minX, v[i].x);
		}
		else if(v[i].x<v[i+1].x)
		{
			// y=a*x+c
			// a=(v[i+1].y-v[i].y)/(v[i+1].x-v[i].x)
			// c=v[i].y-a*v[i].x
			coord a=(v[i+1].y-v[i].y)/(v[i+1].x-v[i].x), c=v[i].y-v[i].x*a;
			down.push_back({a, c});
		}
		else
		{
			coord a=(v[i+1].y-v[i].y)/(v[i+1].x-v[i].x), c=v[i].y-v[i].x*a;
			up.push_back({a, c});
		}
	}
}

void ch(std::vector<line>& up)
{
	std::vector<line> ans;

	std::sort(all(up), [](line l, line m){
		return l.a>m.a || (l.a==m.a && l.c>m.c);
	});

	for(line l : up)
	{
		if(!ans.empty() && ans.back().a==l.a)
			ans.pop_back();
		while(sz(ans)>1 && xintersect(l, ans.back())<=xintersect(l, ans.end()[-2]))
			ans.pop_back();
		ans.push_back(l);
	}

	std::swap(ans, up);
}

void simpRight(std::vector<line>& up, std::vector<line>& down)
{
	while(sz(up)>1 && !down.empty() && down.back().a>up.end()[-2].a && xintersect(down.back(), up.back())>=xintersect(down.back(), up.end()[-2]))
		up.pop_back();
	while(sz(down)>1 && !up.empty() && down.end()[-2].a>up.back().a && xintersect(up.back(), down.back())>=xintersect(up.back(), down.end()[-2]))
		down.pop_back();
}

void simp()
{
	// for(int i=0;i<N;++i)
		// printf("(%Lf, %Lf)\n", v[i].x, v[i].y);
	// printf("\n");

	// for(line l : up)
		// printf("y >= (%Lf) * x + (%Lf)\n", l.a, l.c);
	// for(line l : down)
		// printf("y <= (%Lf) * x + (%Lf)\n", l.a, l.c);
	// printf("\n");

	auto reverse=[](std::vector<line>& L)
	{
		for(line& l : L)
		{
			l.a=-l.a;
			l.c=-l.c;
		}
	};

	auto bounds=[&](std::vector<line>& L)
	{
		while(sz(L)>1 && xintersect(L.back(), L.end()[-2])>=maxX)
			L.pop_back();
		std::reverse(all(L));
		while(sz(L)>1 && xintersect(L.back(), L.end()[-2])<=minX)
			L.pop_back();
		std::reverse(all(L));
	};

	ch(up);
	reverse(down);
	ch(down);
	reverse(down);

	// for(line l : up)
		// printf("y >= (%Lf) * x + (%Lf)\n", l.a, l.c);
	// for(line l : down)
		// printf("y <= (%Lf) * x + (%Lf)\n", l.a, l.c);
	// printf("\n");

	simpRight(up, down);
	reverse(up);
	reverse(down);
	simpRight(down, up);
	reverse(up);
	reverse(down);

	// for(line l : up)
		// printf("y >= (%Lf) * x + (%Lf)\n", l.a, l.c);
	// for(line l : down)
		// printf("y <= (%Lf) * x + (%Lf)\n", l.a, l.c);
	// printf("\n");

	bounds(up);
	bounds(down);

	// for(line l : up)
		// printf("y >= (%Lf) * x + (%Lf)\n", l.a, l.c);
	// for(line l : down)
		// printf("y <= (%Lf) * x + (%Lf)\n", l.a, l.c);
	// printf("\n");
}

coord get()
{
	if(minX>=maxX)
		return 0;

	if(up[0].a>down[0].a)
		minX=std::max(minX, xintersect(up[0], down[0]));
	if(up.back().a<down.back().a)
		maxX=std::min(maxX, xintersect(up.back(), down.back()));

	std::vector<pct> p;
	int i;
	coord x;

	p.push_back({minX, up[0](minX)});
	for(i=1;i<sz(up);++i)
	{
		x=xintersect(up[i-1], up[i]);
		p.push_back({x, up[i](x)});
	}
	p.push_back({maxX, up.back()(maxX)});

	p.push_back({maxX, down.back()(maxX)});
	for(i=sz(down)-1;i>0;--i)
	{
		x=xintersect(down[i-1], down[i]);
		p.push_back({x, down[i](x)});
	}
	p.push_back({minX, down[0](minX)});

	// for(pct a : p)
		// printf("(%Lf, %Lf)\n", a.x, a.y);

	p.push_back(p[0]);
	coord area=0;
	for(i=1;i<sz(p);++i)
		area+=cross({0, 0}, p[i-1], p[i]);

	return std::max(-area*0.5, 0.L);
}

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

	fscanf(f, "%d", &N);
	for(i=0;i<N;++i)
		fscanf(f, "%Lf%Lf", &v[i].x, &v[i].y);

	init();
	simp();
	fprintf(g, "%.02Lf\n", get());

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