Cod sursa(job #2376557)

Utilizator oldatlantianSerban Cercelescu oldatlantian Data 8 martie 2019 16:20:33
Problema Camera Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 4.11 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(EPS), sin(EPS)); // 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)) {
			if ((l.b < res.back().b) ^ tmp)
				res.pop_back();
			else
				continue; }

		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

	for (int st = n - 1, dr = 1, i = 0; i < n; ++i, st = (++st == n ? 0 : st), dr = (++dr == n ? 0 : dr)) {
		if (!cross(pts[i], pts[st], pts[dr]) < EPS)
			continue;

		if (cadran(pts[st]  - pts[dr]) / 2 == 0) {  // line(i, dr) points up, line(i, st) points down
			up.emplace_back(
				(pts[dr].imag() - pts[i].imag()) / (pts[dr].real() - pts[i].real()),
				pts[dr].imag() - pts[dr].real() * (pts[dr].imag() - pts[i].imag()) / (pts[dr].real() - pts[i].real()));
			dn.emplace_back(
				(pts[st].imag() - pts[i].imag()) / (pts[st].real() - pts[i].real()),
				pts[st].imag() - pts[st].real() * (pts[st].imag() - pts[i].imag()) / (pts[st].real() - pts[i].real())); }
		else { // vice versa
			dn.emplace_back(
				(pts[dr].imag() - pts[i].imag()) / (pts[dr].real() - pts[i].real()),
				pts[dr].imag() - pts[dr].real() * (pts[dr].imag() - pts[i].imag()) / (pts[dr].real() - pts[i].real()));
			up.emplace_back(
				(pts[st].imag() - pts[i].imag()) / (pts[st].real() - pts[i].real()),
				pts[st].imag() - pts[st].real() * (pts[st].imag() - pts[i].imag()) / (pts[st].real() - pts[i].real())); } }

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

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

	make_batch(up);
	tmp = true;
	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; }