题意：
有一个连通器，由两个漏斗组成（关于漏斗的描述见描述）。
现向漏斗中注入一定量的水，问最终水的绝对位置（即y轴坐标）
思路：
总体来说分为3种情况。
1.两个漏斗可能同时装有水。
2.只可能a漏斗有水。
3.只可能b漏斗有水。
于是可以二分枚举y的坐标。
关键在于对于某个y坐标来说，要求出新的交点，再求面积。
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <algorithm>
#include <iostream>
using namespace std; const int maxn = ;
const double eps = 1e-;
const double inf = 999999999.99; struct Point{
double x,y;
}a[ maxn ],b[ maxn ],res[ maxn ],amid,bmid; double xmult( Point a,Point b,Point c ){
double ans = (a.x-c.x)*(b.y-c.y) - (a.y-c.y)*(b.x-c.x);
return ans;
} int cmp( Point a,Point b ){
if( a.x!=b.x ) return a.x<b.x;
else return a.y>b.y;
} double area( Point pnt[],int n ){
double ans = ;
for( int i=;i<n-;i++ ){
ans += xmult( pnt[],pnt[i],pnt[i+] );
}
return fabs( 0.5*ans );
} int main(){
//freopen("out.txt","w",stdout);
int T;
scanf("%d",&T);
while( T-- ){
double aim;
double ansY = ;
scanf("%lf",&aim);
int n1,n2;
scanf("%d",&n1);
double ymax = inf;
int flag1 = -;
for( int i=;i<n1;i++ ){
scanf("%lf%lf",&a[i].x,&a[i].y);
if( ymax>a[i].y ){
ymax = a[i].y;
flag1 = i;
}
}
amid = a[ flag1 ];
scanf("%d",&n2);
ymax = inf;
int flag2 = -;
for( int i=;i<n2;i++ ){
scanf("%lf%lf",&b[i].x,&b[i].y);
if( ymax>b[i].y ){
ymax = b[i].y;
flag2 = i;
}
}
bmid = b[ flag2 ];
//input
double aYmin = min( a[].y,a[n1-].y );
double bYmin = min( b[].y,b[n2-].y );
//printf("aYmin = %lf bYmin = %lf\n",aYmin,bYmin);
double abYmax = max( aYmin,bYmin );
double abYmin = min( amid.y,bmid.y );
double L ,R ;
//printf("L = %lf , R = %lf \n",L,R);
int special = -;
if( aYmin<=bmid.y )//a is lower
{
special = ;
}
else if( bYmin<=amid.y )
{
special = ;
}
if( special==- ){
L = abYmin;
R = min( aYmin,bYmin );
while( L<R ){
double mid = (L+R)/2.0;
double sumArea = ;
/*******solve b******/
//printf("mid = %lf\n",mid);
if( mid>bYmin ){
int cnt = ;
double newY = bYmin;
int f = -;
for( int i=;i<n2;i++ ){
if( b[i].y<=newY ){
res[ cnt++] = b[ i ];
f = i;
}
else break;
}
if( f==- ){}
else{
Point tmp;
tmp.y = newY;
tmp.x = (b[ f+ ].x-b[ f ].x)*(newY-b[f].y)/(b[f+].y-b[f].y) + b[f].x;
res[ cnt++ ] = tmp;
}
sumArea += area( res,cnt );
}
else if( mid<=bmid.y ){}
else{
//printf("here\n");
int cnt = ;
int f = -;
for( int i=;i<n2;i++ ){
if( b[i].y<=mid ){
f = i;
break;
}
}
//printf("f = %d\n",f);
Point tmp;
tmp.y = mid;
tmp.x = b[f].x-( (b[f].x-b[f-].x)*(mid-b[f].y)/(b[f-].y-b[f].y) );
res[ cnt++] = tmp;
for( int i=f;i<n2;i++ ){
if( b[i].y<mid ){
res[ cnt++ ] = b[i];
f = i;
}
else break;
}
tmp.y = mid;
tmp.x = (b[ f+ ].x-b[ f ].x)*(mid-b[f].y)/(b[f+].y-b[f].y) + b[f].x;
res[ cnt++ ] = tmp;
//printf("cnt = %d\n",cnt);
sumArea += area( res,cnt );
}
//printf("sumarea = %lf \n",sumArea);
/********solve a *****/
if( mid>aYmin ){
int cnt = ;
double newY = aYmin;
int f = -;
for( int i=;i<n1;i++ ){
if( a[i].y<=newY ){
res[ cnt++] = a[ i ];
f = i;
}
else break;
}
if( f==- ){}
else{
Point tmp;
tmp.y = newY;
tmp.x = (a[ f+ ].x-a[ f ].x)*(newY-a[f].y)/(a[f+].y-a[f].y) + a[f].x;
res[ cnt++ ] = tmp;
}
sumArea += area( res,cnt );
}
else if( mid<=amid.y ){}
else{
int cnt = ;
int f = -;
for( int i=;i<n1;i++ ){
if( a[i].y<=mid ){
f = i;
break;
}
}
Point tmp;
tmp.y = mid;
tmp.x = a[f].x-( (a[f].x-a[f-].x)*(mid-a[f].y)/(a[f-].y-a[f].y) );
res[ cnt++] = tmp;
for( int i=f;i<n1;i++ ){
if( a[i].y<mid ){
res[ cnt++ ] = a[i];
f = i;
}
else break;
}
tmp.y = mid;
tmp.x = (a[ f+ ].x-a[ f ].x)*(mid-a[f].y)/(a[f+].y-a[f].y) + a[f].x;
res[ cnt++ ] = tmp;
sumArea += area( res,cnt );
}
//printf("sumarea2 = %lf\n\n\n",sumArea);
if( fabs(sumArea-aim)<=eps ){
ansY = mid;
break;
}
else if( sumArea>aim ){
R = mid-eps;
}
else {
L = mid+eps;
ansY = mid;
}
}
}//ab可能都同时都有水
else{
//printf("special = %d\n",special);
double sumArea = ;
if( special== ){//‘1’表示只有a会有水
double L = amid.y;
double R = aYmin;
while( L<R ){
double mid = (L+R)/2.0;
//printf("mid = %lf\n",mid);
int cnt = ;
int f = -;
for( int i=;i<n1;i++ ){
if( a[i].y<=mid ){
f = i;
break;
}
}
Point tmp;
tmp.y = mid;
tmp.x = a[f].x-( (a[f].x-a[f-].x)*(mid-a[f].y)/(a[f-].y-a[f].y) );
res[ cnt++] = tmp;
for( int i=f;i<n1;i++ ){
if( a[i].y<mid ){
res[ cnt++ ] = a[i];
f = i;
}
else break;
}
tmp.y = mid;
tmp.x = (a[ f+ ].x-a[ f ].x)*(mid-a[f].y)/(a[f+].y-a[f].y) + a[f].x;
res[ cnt++ ] = tmp;
sumArea += area( res,cnt );
//printf("cnt = %d\n",cnt);
//printf("sumarea = %lf\n",sumArea);
if( fabs(sumArea-aim)<=eps ){
ansY = mid;
break;
}
else if( sumArea>aim ) {
R = mid-eps;
}
else {
L = mid + eps;
ansY = L;
}
}
}
else{//'2'表示只有b会有水
double L = bmid.y;
double R = bYmin;
//printf("L = %lf,R = %lf\n",L,R);
while( L<R ){
double mid = (L+R)/2.0;
//printf("mid = %lf\n",mid);
int cnt = ;
int f = -;
for( int i=;i<n2;i++ ){
if( b[i].y<=mid ){
f = i;
break;
}
}
Point tmp;
tmp.y = mid;
tmp.x = b[f].x-( (b[f].x-b[f-].x)*(mid-b[f].y)/(b[f-].y-b[f].y) );
res[ cnt++] = tmp;
for( int i=f;i<n2;i++ ){
if( b[i].y<mid ){
res[ cnt++ ] = b[i];
f = i;
//printf("add : i = %d\n",i);
}
else break;
}
tmp.y = mid;
tmp.x = (b[ f+ ].x-b[ f ].x)*(mid-b[f].y)/(b[f+].y-b[f].y) + b[f].x;
res[ cnt++ ] = tmp;
//printf("cnt = %d\n",cnt);
sumArea += area( res,cnt );
if( fabs(sumArea-aim)<=eps ){
ansY = mid;
break;
}
else if( sumArea>aim ) {
R = mid-eps;
}
else {
L = mid + eps;
ansY = L;
}
}
}
}
printf("%.3lf\n",ansY);
}
return ;
}