首页 > ACM题库 > HDU-杭电 > HDU 3119-ChaeYeon[解题报告]HOJ
2014
03-02

HDU 3119-ChaeYeon[解题报告]HOJ

ChaeYeon

问题描述 :

Chae Yeon is a popular pop female singer who rose to fame with her amazing sexy dance style and the sounds of nature voice she has. She proved to be a great dancer, and she showed off her vocals in her live performances. If you had ever seen her dance, I bet you’d love it.
I felt stage lighting interesting when I was enjoying Chae Yeon’s performance. We all know that stage lighting instruments are used for the concerts and other performances taking place in live performance venues. They are also used to light the stages. Actually this is a color mixing process. There are two types of color mixing: Additive and Subtractive. Most stages use the former and in this case there are three primary colors: red, green, and blue. In the absence of color, or when no colors are showing, the stage is black. If all three primary colors are showing, the result is white. When red and green combine together, the result is yellow. When red and blue combine together, the result is magenta. When blue and green combine together, the result is cyan. When two same color combine together, the result is still that color.
Arbiter

We have got the coordinate and the primary color of the figure that each Stage Lighting Instrument sent out. For simplicity’s sake, we can just treat the figure as a circle. Of course we’ll know the radius of each colored circle. Some color may be changed based on the Color Mixed Theory we mentioned above. Can you find the area of each color?

输入:

The first line consists of an integer T, indicating the number of test cases.
The first line of each case consists of three integers R, G, B, indicating the number of red circles, green circles and blue circles. The next R + G + B lines, each line consists of three integer x, y, r, indicating the coordinate and the radius. The first R lines descript the red circles, the second G lines descript the green circles and the last B lines descript the blue circles.

输出:

The first line consists of an integer T, indicating the number of test cases.
The first line of each case consists of three integers R, G, B, indicating the number of red circles, green circles and blue circles. The next R + G + B lines, each line consists of three integer x, y, r, indicating the coordinate and the radius. The first R lines descript the red circles, the second G lines descript the green circles and the last B lines descript the blue circles.

样例输入:

1
1 1 1
0 2 3
2 0 3
-2 0 3

样例输出:

9.28 15.04 15.04 4.92 7.04 7.04 1.28

Hint
Gentleman’s Reminder: please make sure that your program won’t output “-0.00”.

#include<stdio.h>
#include<math.h>
#include<algorithm>
#define PI 3.14159265358979323846
#define eps 1e-8
using namespace std;

inline int SGN(double x){return x < -eps ? -1 : x < eps ? 0 : 1;}
inline double SQR(double x){return x * x;}

struct pt
{
	double x, y;
	pt(){}
	pt(double _x, double _y):x(_x), y(_y){}
	pt operator - (const pt p1){return pt(x - p1.x, y - p1.y);}
	pt operator + (const pt p1){return pt(x + p1.x, y + p1.y);}
	pt operator * (double r){return pt(x * r, y * r);}
	pt operator / (double r){return pt(x / r, y / r);}
	void read(){scanf("%lf %lf", &x, &y);}
};

inline double cpr(const pt &a,const pt &b){return a.x*b.y-a.y*b.x;}
inline double dis(const pt &a, const pt &b){return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));}
inline double dis2(const pt &a, const pt &b){return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);}

inline void intersection_circle_circle(pt &c1, double r1, pt &c2, double r2, pt &p1, pt &p2)
{
	double d2 = (c1.x - c2.x) * (c1.x - c2.x) + (c1.y - c2.y) * (c1.y - c2.y);
	double cos = (r1 * r1 + d2 - r2 * r2) / (2 * r1 * sqrt(d2));
	pt v1 = (c2 - c1) / dis(c1, c2), v2 = pt(-v1.y, v1.x) * (r1 * sqrt(1 - cos * cos));
	pt X = c1 + v1 * (r1 * cos);
	p1 = X + v2;
	p2 = X - v2;
}

struct Event
{
	double pos;
	int del;
	pt X;
	bool operator < (const Event e)const{return pos < e.pos;}
};


///////////////////////////////////////////////////

int n;
pt o[400];
double r[400];

Event e[800];
int cnt;

double ans[10];
int sc[400];

//0:a��b	1:b��a	2:�ཻ	3:����
inline int rlt(int a, int b)
{
	double d = dis2(o[a], o[b]), df = SGN(d - SQR(r[a] - r[b]));
	if (df <= 0)return !SGN(r[a] - r[b]) ? a < b : r[a] < r[b];
	return d < SQR(r[a] + r[b]) - eps ? 2 : 3;
}

inline double arcArea(double r, Event e1, Event e2)
{
	double dif = e2.pos - e1.pos;
	return (cpr(e1.X, e2.X) + (dif - sin(dif)) * r * r) * 0.5;
}

void solve()
{
	double center, d2, ang, angX, angY;
	pt X, Y, L;
	Event last;
	memset(ans, 0, sizeof(ans));
	
	for (int i = 0; i < n; i++) if (r[i] > eps)
	{
		int acc[4] = {0};
		cnt = 0;
		L = pt(o[i].x - r[i], o[i].y);
		e[cnt].pos = -PI, e[cnt].del = sc[i], e[cnt++].X = L;
		e[cnt].pos = PI, e[cnt].del = -sc[i], e[cnt++].X = L;
		for (int j = 0; j < n; j++) if (i != j && r[j] > eps)
		{
			int rel = rlt(i, j);
			if (rel == 1)
			{
				e[cnt].pos = -PI, e[cnt].del = sc[j], e[cnt++].X = L;
				e[cnt].pos = PI, e[cnt].del = -sc[j], e[cnt++].X = L;
			} else if (rel == 2)
			{
				intersection_circle_circle(o[i], r[i], o[j], r[j], X, Y);
				angX = atan2(X.y - o[i].y, X.x - o[i].x);
				angY = atan2(Y.y - o[i].y, Y.x - o[i].x);
				if (angX < angY) acc[sc[j]]++;
				e[cnt].pos = angY, e[cnt].del = sc[j], e[cnt++].X = Y;
				e[cnt].pos = angX, e[cnt].del = -sc[j], e[cnt++].X = X;
			}
		}
		sort(e, e + cnt);
		last.pos = -PI, last.X = pt(o[i].x - r[i], o[i].y);
		for (int j = 0; j < cnt; j++)
		{
			double tmp = arcArea(r[i], last, e[j]);
			ans[!!acc[1] + 2 * !!acc[2] + 4 * !!acc[3]] += tmp;
			ans[!!(acc[1] - (sc[i] == 1)) + 2 * !!(acc[2] - (sc[i] == 2)) + 4 * !!(acc[3] - (sc[i] == 3))] -= tmp;
			acc[abs(e[j].del)] += SGN(e[j].del);
			last = e[j];
		}
	}
}

void fuck()
{
	int n1, n2, n3;
	scanf("%d %d %d", &n1, &n2, &n3);
	n = n1 + n2 + n3;
	for (int i = 0; i < n; i++)
	{
		o[i].read();
		scanf("%lf", &r[i]);
		sc[i] = i < n1 ? 1 : i < n1 + n2 ? 2 : 3;
	}
	solve();
	printf("%.2f %.2f %.2f %.2f %.2f %.2f %.2f\n", fabs(ans[1]), fabs(ans[2]), fabs(ans[4]), fabs(ans[7]), fabs(ans[3]), fabs(ans[5]), fabs(ans[6]));
}


int main()
{
	int tc;
	scanf ("%d", &tc);
	while (tc--)fuck();
	return 0;
}