1 /*
2 * SOUR:pku3334
3 * ALGO:二分高度，求水平线和多边形的交点，求出多边形面积
4 * DATE: 2010年 07月 07日 星期三 22:29:14 CST
5 * */
6 const int N = 1024;
7 struct point_t {
8 double x, y;
9 point_t (){}
10 point_t (double a, double b){x = a, y = b;}
11 }P[N], Q[N];
12 int m, n, cp, cq;
13 double area;
14
15 point_t operator + (point_t a, point_t b) { return point_t(a.x + b.x, a.y + b.y);}
16 point_t operator - (point_t a, point_t b) { return point_t(a.x - b.x, a.y - b.y);}
17 double SQR(double x ){ return x * x;}
18 double dist(point_t a) { return sqrt(SQR(a.x) + SQR(a.y));}
19 double dist(point_t a, point_t b) { return dist(a-b);}
20 double cross_mul(point_t a, point_t b) { return a.x * b.y - a.y * b.x;}
21 const double eps = 1e-10;
22
23 double calcu(point_t p[], int n, int cusp, double h)
24 {
25 double ans = 0;
26 int i, j, k, beg = 0, end = n - 1;
27 if (h <= p[cusp].y) {
28 return 0;
29 }
30 for (i = 0;i < cusp;i ++) {
31 if (p[i].y >= h && h >= p[i+1].y) {
32 beg = i;break;
33 }
34 }
35 for (i = n - 2;i >= cusp;i--) {
36 if (p[i].y <= h && h <= p[i+1].y) {
37 end = i;break;
38 }
39 }
40
41 point_t a = point_t(p[beg].x + (h - p[beg].y) * (p[beg+1].x - p[beg].x)
42 / (p[beg+1].y - p[beg].y) , h);
43 point_t b = point_t(p[end].x + (h - p[end].y) * (p[end+1].x - p[end].x)
44 / (p[end+1].y - p[end].y) , h);
45 ans += cross_mul(a, p[beg+1]) + cross_mul(p[end], b) + cross_mul(b, a);
46 for (i = beg + 1;i <= end - 1;i++) {
47 ans += cross_mul(p[i], p[i+1]);
48 }
49 return fabs(ans / 2.0);
50 }
51
52 int main()
53 {
54 int testcase, i;
55 scanf("%d", &testcase);
56 while (testcase--) {
57 scanf("%lf", &area);
58 scanf("%d", &m); for (i = 0;i < m;i++) { scanf("%lf %lf", &P[i].x, &P[i].y); }
59 scanf("%d", &n); for (i = 0;i < n;i++) { scanf("%lf %lf", &Q[i].x, &Q[i].y); }
60 for (i = 1;i < m-1;i++) {
61 if (P[i-1].y >= P[i].y && P[i].y <= P[i+1].y) {
62 cp = i;
63 }
64 }
65 for (i = 1;i < n-1;i++) {
66 if (Q[i-1].y >= Q[i].y && Q[i].y <= Q[i+1].y) {
67 cq = i;
68 }
69 }
70 double L = min(P[cp].y , Q[cq].y),
71 R = min(min(P[0].y, P[m - 1].y) , min(Q[0].y, Q[n - 1].y)) ;
72 while (L + eps < R) {
73 double mid = (L + R) / 2.0;
74 double A = calcu(P, m, cp, mid) + calcu(Q, n, cq, mid);
75 //printf("h = %.3f, A = %.3f\n", mid, A);
76 if (A <= area) {
77 L = mid;
78 }else {
79 R = mid;
80 }
81 }
82 printf("%.3f\n", L);
83 }
84 return 0;
85 }
86
87
88