Cod sursa(job #2376680)

Utilizator oldatlantianSerban Cercelescu oldatlantian Data 8 martie 2019 17:04:44
Problema Camera Scor 100
Compilator cpp-64 Status done
Runda Lista lui wefgef Marime 3.48 kb
#include <bits/stdc++.h>
#define rev(v) (v.rbegin())
using namespace std;

ifstream fi("camera.in");
ofstream fo("camera.out");

using f64 = double;
using cpx = complex<f64>;

const f64 EPS = 1e-6;
const cpx ROT = cpx(cos(sqrt(7)), sin(sqrt(7))); // random angle rotation, chosen by a fair dice roll

struct Line {
	f64 a, b;
	Line(f64 _a, f64 _b) {
		a = _a, b = _b; }
	Line() {
		a = 0, b = 1e18; }
	inline f64 operator () (const f64 &x) {
		return a * x + b; } };
 

vector<Line> up, dn;
vector<cpx> pts;
int n;
bool tmp;

static int cadran(const cpx &point) {
	if (point.real() > 0 && point.imag() > 0)
		return 0;
	if (point.real() < 0 && point.imag() > 0)
		return 1;
	if (point.real() < 0 && point.imag() < 0)
		return 2;
	if (point.real() > 0 && point.imag() < 0)
		return 3; }

static f64 intersect(const Line &u, const Line &v) {
	return (v.b - u.b) / (u.a - v.a); }

static inline bool eq(f64 a, f64 b) {
	return abs(a - b) < EPS; }

static f64 cross(cpx p, cpx a, cpx b) {
	a-= p;
	b-= p;
	return (a.real() * b.imag()) - (a.imag() * b.real()); }

static void make_batch(vector<Line> &bat) {
	vector<Line> res;
	for (const auto &l: bat) {
		if (!res.empty() && eq(l.a, res.back().a))
				res.pop_back();

		while (res.size() >= 2 && intersect(rev(res)[1], rev(res)[0]) > intersect(rev(res)[1], l))
			res.pop_back();
		res.push_back(l); }

	bat = res; }

int main() {
	fi >> n;
	pts.resize(n);
	for (auto &p: pts) {
		f64 x, y;
		fi >> x >> y;
		p = cpx(x, y) * ROT + ROT; } // affine transformation

	f64 sarea(0);
	for (int st = 0, dr = 1; st < n; ++st, dr = (++dr == n ? 0 : dr))
		sarea+= cross(0, pts[st], pts[dr]);
	if (sarea >= 0)
		reverse(begin(pts), end(pts));

	for (int st = 0, dr = 1; st < n; ++st, dr = (++dr == n ? 0 : dr)) {
		auto &v = ((pts[dr].real() < pts[st].real()) ? up : dn);

		v.emplace_back(
			(pts[dr].imag() - pts[st].imag()) / (pts[dr].real() - pts[st].real()),
			pts[dr].imag() - pts[dr].real() * (pts[dr].imag() - pts[st].imag()) / (pts[dr].real() - pts[st].real())); }

	sort(begin(dn), end(dn), [&](const Line &u, const Line &v) {
		if (eq(u.a, v.a))
			return u.b > v.b;
		return u.a > v.a; });

	sort(begin(up), end(up), [&](const Line &u, const Line &v) {
		if (eq(u.a, v.a))
			return u.b < v.b;
		return u.a < v.a; });

	make_batch(up);
	make_batch(dn);

	f64 mn(1e18), mx(-1e18);
	for (int i = 0; i < up.size(); ++i)
	for (int j = 0; j < dn.size(); ++j) {
		Line &u = up[i];
		Line &v = dn[j];
		if (eq(u.a, v.a))
			continue;

		f64 si = (i == 0 ? -1e18 : intersect(up[i], up[i - 1]));
		f64 sj = (j == 0 ? -1e18 : intersect(dn[j], dn[j - 1]));
		f64 ei = (i + 1 == up.size() ? 1e18 : intersect(up[i], up[i + 1]));
		f64 ej = (j + 1 == dn.size() ? 1e18 : intersect(dn[j], dn[j + 1]));

		f64 x = intersect(u, v);
		if (si - EPS <= x && x <= ei + EPS)
		if (sj - EPS <= x && x <= ej + EPS) {
			mn = min(mn, x);
			mx = max(mx, x); } }

	fo << setprecision(2) << fixed;
	if (eq(mn, mx)) {
		fo << 0.0 << endl;
		return 0; }

	f64 ant(0);
	for (int i = 0; i < up.size(); ++i) {
		f64 si = (i == 0 ? -1e18 : intersect(up[i], up[i - 1]));
		f64 ei = (i + 1 == up.size() ? 1e18 : intersect(up[i], up[i + 1]));
		si = max(si, mn);
		ei = min(ei, mx);
		ant+= (up[i](si) + up[i](ei)) * max(0.0, ei - si) / 2; }

	for (int i = 0; i < dn.size(); ++i) {
		f64 si = (i == 0 ? -1e18 : intersect(dn[i], dn[i - 1]));
		f64 ei = (i + 1 == dn.size() ? 1e18 : intersect(dn[i], dn[i + 1]));
		si = max(si, mn);
		ei = min(ei, mx);
		ant-= (dn[i](si) + dn[i](ei)) * max(0.0, ei - si) / 2; }

	fo << abs(ant) << endl;

	return 0; }