Cod sursa(job #2415902)

Utilizator LucaSeriSeritan Luca LucaSeri Data 26 aprilie 2019 16:51:54
Problema Camera Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.5 kb
#include <bits/stdc++.h>
 
using namespace std;

#define all(x) (x).begin(), (x).end()
typedef double ld;

struct Point {
	ld x, y;
	Point() : x(0), y(0) {}
	Point(const ld &x, const ld &y) : x(x), y(y) {}

	Point operator + (const Point &o) {
		return {x + o.x, y + o.y};
	}
	Point operator - (const Point &o) {
		return {x - o.x, y - o.y};
	}
	Point operator *(const ld &o) {
		return {x*o, y*o};
	}
	Point operator /(const ld &o) {
		return {x/o, y/o};
	}
	ld operator *(const Point &o) {
		return x*o.x + y*o.y; 
	}
	ld operator ^(const Point &o) {
		return x*o.y - y*o.x;
	}

	const bool operator < (const Point &o) {
		if(x == o.x) return y < o.y;
		return x < o.x;
	}
	ld angle() {
		return atan2(y, x);
	}
};

using Poly = vector< Point >;
using HalfPlane = pair< Point, Point >; /// Start si directie

Point intersect(Point a, Point ab, Point c, Point cd) {
	return a + ab*(((c-a)^cd)/(ab^cd));
}

Poly cutPoly(Poly &v, HalfPlane hp) {
	Poly ret = Poly();

	for(int i = 0; i < v.size(); ++i) {
		ld curCross = (v[i]-hp.first)^hp.second;
		ld nextCross = (v[(i+1)%v.size()]-hp.first)^hp.second;
		if(curCross <= 0) {
			ret.emplace_back(v[i]);
		}
		if(curCross*nextCross < 0) {
			ret.emplace_back(intersect(v[i], v[(i+1)%v.size()]-v[i], hp.first, hp.second));
		} 
	}

	return ret;
}

int main() { 
	#ifdef BLAT
		freopen("input", "r", stdin);
	#else
		freopen("camera.in", "r", stdin);
		freopen("camera.out", "w", stdout);
	#endif
 
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	srand(time(nullptr));

	int n;
	cin >> n;

	Poly v(n);
	
	for(int i = 0; i < n; ++i) {
		int x, y;
		cin >> x >> y;
		v[i] = Point(x, y);
	}

	Poly eu;
	eu.emplace_back(-1e5, -1e5);
	eu.emplace_back(-1e5, 1e5);
	eu.emplace_back(1e5, 1e5);
	eu.emplace_back(1e5, -1e5);

	for(int i = 0; i < n - 1; ++i) {
		eu = cutPoly(eu, {v[i], v[i + 1] - v[i]});
		if(eu.size() <= 2) break;
	}

	eu = cutPoly(eu, {v[n-1], v[0] - v[n-1]});
	if(eu.size() != 0) {
		ld ans = 0;
		for(int i = 0; i < eu.size() - 1; ++i) {
			ans += (eu[i]^eu[i+1]);
		}
		ans += eu.back()^eu[0];
		cout << setprecision(2) << fixed << abs(ans*0.5) << '\n';
		return 0;
	}

	eu.emplace_back(-1e5, -1e5);
	eu.emplace_back(-1e5, 1e5);
	eu.emplace_back(1e5, 1e5);
	eu.emplace_back(1e5, -1e5);

	for(int i = 1; i < n; ++i) {
		eu = cutPoly(eu, {v[i], v[i-1] - v[i]});
	}

	eu = cutPoly(eu, {v[0], v[n-1] - v[0]});
	ld ans = 0;
	for(int i = 0; i < eu.size() - 1; ++i) {
		ans += (eu[i]^eu[(i+1)]);
	}
	ans += eu.back()^eu[0];
	cout << setprecision(2) << fixed << abs(ans*0.5) << '\n';
	return 0;
}