Circles problem

solution.cpp

#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES

#include <iostream>
#include <fstream>

#include <string>
#include <vector>

#include <cmath>
#include <math.h>
#include <algorithm>

#define fi(i, a, b) for(int i = a; i < b; i++)
#define int long long

using namespace std;

double Epsilon = 0.00001;

double r2s(double r)
{
	return M_PI * r * r / 2;
}

bool eq(double d1, double d2)
{
	return abs(d1 - d2) < Epsilon;
}

bool le(double d1, double d2)
{
	return d1 < d2 || eq(d1, d2);
}

bool ge(double d1, double d2)
{
	return d1 > d2 || eq(d1, d2);
}

class vector2
{
public:
	double x, y;

	vector2() : x(0), y(0) {}
	vector2(double x, double y) : x(x), y(y) {}

	bool operator==(vector2 other)
	{
		return eq(x, other.x) && eq(y, other.y);
	}

	vector2 operator +(vector2 other)
	{
		return vector2(x + other.x, y + other.y);
	}

	vector2 operator -(vector2 other)
	{
		return vector2(x - other.x, y - other.y);
	}

	vector2 operator *(double a)
	{
		return vector2(x * a, y * a);
	}

	vector2 operator /(double a)
	{
		return vector2(x / a, y / a);
	}

	double length()
	{
		return sqrt(dot(*this));
	}

	vector2 normalized()
	{
		return *this / this->length();
	}

	double dot(vector2 other)
	{
		return x * other.x + y * other.y;
	}

	double cross(vector2 other)
	{
		return x * other.y - y * other.x;
	}

	double angle(vector2 other)
	{
		return acos(this->normalized().dot(other.normalized()));
	}
};

class circle
{
public:
	double r;
	vector2 pos;

	circle() : r(0) {}
	circle(vector2 pos, double r) : pos(pos), r(r) {}

	bool operator==(circle other)
	{
		return eq(r, other.r) && pos == other.pos;
	}

	double intersect(circle other)
	{
		float d = (pos - other.pos).length();

		if (ge(d, r + other.r))
		{
			return 0;
		}

		double R = other.r;

		double r2 = r * r;
		double R2 = R * R;
		double d2 = d * d;

		double b1 = (d2 + r2 - R2) / (2 * d * r);
		double b2 = (d2 + R2 - r2) / (2 * d * R);
		
		b1 = fitToRange(-1, 1, b1);
		b2 = fitToRange(-1, 1, b2);

		return r2 * acos(b1) + R2 * acos(b2) -
			1.0 / 2 * sqrt((-d + r + R) * (d + r - R) * (d - r + R) * (d + r + R));
	}

	double fitToRange(double mn, double mx, double val)
	{
		val = min(val, mx);
		val = max(val, mn);

		return val;
	}

	double space()
	{
		return r2s(r);
	}
};

void main()
{
#ifdef DEBUG
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif // DEBUG

	double w, h;
	int n;

	cin >> w >> h >> n;

	vector<circle> cs;

	double result = w * h;

	fi(i, 0, n)
	{
		double x, y, r;
		cin >> x >> y >> r;

		circle c(vector2(x, y), r);
		result -= c.space();

		fi(j, 0, cs.size())
		{
			result += c.intersect(cs[j]);
		}

		cs.push_back(c);
	}

	cout << result << endl;
}