Cod sursa(job #2415957)

Utilizator LucaSeriSeritan Luca LucaSeri Data 26 aprilie 2019 17:31:01
Problema Camera Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.44 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(-1e6, -1e6);
	eu.emplace_back(-1e6, 1e6);
	eu.emplace_back(1e6, 1e6);
	eu.emplace_back(1e6, -1e6);
 
	for(int i = 0; i < n; ++i) {
		eu = cutPoly(eu, {v[i], v[(i+1)%n] - v[i]});
	}
 
	ld ans1 = 0;
	for(int i = 0; i < eu.size(); ++i) {
		ans1 += (eu[i]^eu[(i+1)%eu.size()]);
	}

 	eu.clear();
	eu.emplace_back(-1e6, -1e6);
	eu.emplace_back(-1e6, 1e6);
	eu.emplace_back(1e6, 1e6);
	eu.emplace_back(1e6, -1e6);
 
	for(int i = 0; i < n; ++i) {
		eu = cutPoly(eu, {v[i], v[(i+n-1)%n] - v[i]});
	}
 
	ld ans = 0;
	for(int i = 0; i < eu.size(); ++i) {
		ans += (eu[i]^eu[(i+1)%eu.size()]);
	}
	ans = abs(ans);
	ans1 = abs(ans1);
	const ld eps = 1e-3;
	if(ans > eps && ans1 > eps) {
		cout << "0.00\n";
		return 0;
	}
	cout << setprecision(2) << fixed << (max(abs(ans), abs(ans1)) + 0.000001)*.5 << '\n';
	return 0;
}