1 #include <iostream>  2 #include<cstdio>  3 #include<cstring>  4 #include<algorithm>  5 #include<stdlib.h>  6 #include<vector>  7 #include<cmath>  8 #include<queue>  9 #include<set> 10 using namespace std; 11 #define N 2010 12 #define LL long long 13 #define INF 0xfffffff 14 const double eps = 1e-8; 15 const double pi = acos(-1.0); 16 const double inf = ~0u>>2; 17 struct point 18 { 19     double x ,y; 20     point(double x=0,double y=0):x(x),y(y){} 21 }p[N],q[N],ch[N]; 22 double minz; 23 int n,m; 24 typedef point pointt; 25 pointt operator -(point a,point b) 26 { 27     return point(a.x-b.x,a.y-b.y); 28 } 29 int dcmp(double x) 30 { 31     if(fabs(x)<eps) return 0; 32     return x<0?-1:1; 33 } 34 double dis(point a) 35 { 36     return sqrt(a.x*a.x+a.y*a.y); 37 } 38 double cross(point a,point b) 39 { 40     return a.x*b.y-a.y*b.x; 41 } 42 double getarea(int n,point p[]) 43 { 44     int i; 45     double s = 0; 46     for(i = 2; i < n ; i++) 47     s+=cross(p[i]-p[1],p[i+1]-p[1]); 48     return s/2; 49 } 50 double cal(double r,point p[],int n) 51 { 52     int i,j; 53     int k = 1; 54     for(i = 1; i <= n; i++) 55     if(p[i].y<p[k].y)    k = i; 56  57     if(dcmp(r-p[k].y)<=0) return 0.0; 58  59     point p1,p2; 60     int g = 0; 61     for(i = 1; i < k; i++) 62     if(dcmp(p[i].y-r)>=0&&dcmp(p[i+1].y-r)<0) 63     { 64         p1.y = r; 65         double d = r-p[i+1].y; 66         p1.x = d*(p[i].x-p[i+1].x)/(p[i].y-p[i+1].y)+p[i+1].x; 67         break; 68     } 69  70     for(j = k ; j >= i+1; j--) 71     ch[++g] = p[j]; 72     ch[++g] = p1; 73     for(i = k+1 ; i <= n; i++) 74     if(dcmp(p[i-1].y-r)<0&&dcmp(p[i].y-r)>=0) 75     { 76         p2.y = r; 77         double d = r-p[i-1].y; 78         p2.x = d*(p[i].x-p[i-1].x)/(p[i].y-p[i-1].y)+p[i-1].x; 79         break; 80     } 81     ch[++g] = p2; 82     for(j = i-1 ; j > k; j--) 83     ch[++g] = p[j]; 84  85     return fabs(getarea(g,ch)); 86 } 87 int main() 88 { 89     int t,i,a; 90     cin>>t; 91     while(t--) 92     { 93         scanf("%d",&a); 94         scanf("%d",&n); 95         minz = INF; 96         double maxz  = INF; 97         for(i = 1; i <= n ;i++) 98         { 99             scanf("%lf%lf",&p[i].x,&p[i].y);100             maxz = min(maxz,p[i].y);101         }102         scanf("%d",&m);103         for(i = 1; i <= m ;i++)104         {105             scanf("%lf%lf",&q[i].x,&q[i].y);106             maxz = min(maxz,p[i].y);107         }108         minz = min(min(p[1].y,p[n].y),min(q[1].y,q[m].y));109         double lef = maxz,rig = minz,mid;110         while(fabs(rig-lef)>eps)111         {112             mid = (rig+lef)/2.0;113             double s1 = cal(mid,p,n),s2 = cal(mid,q,m);114             if(dcmp(s1+s2-a)>0)115             rig = mid;116             else lef = mid;117         }118         printf("%.3f\n",lef);119     }120     return 0;121 }

  1 #include <iostream>  2 #include<cstdio>  3 #include<cstring>  4 #include<algorithm>  5 #include<stdlib.h>  6 #include<vector>  7 #include<cmath>  8 #include<queue>  9 #include<set> 10 using namespace std; 11 #define N 2010 12 #define LL long long 13 #define INF 0xfffffff 14 const double eps = 1e-8; 15 const double pi = acos(-1.0); 16 const double inf = ~0u>>2; 17 struct point 18 { 19     double x ,y; 20     point(double x=0,double y=0):x(x),y(y){} 21 }p[N],q[N],ch[N]; 22 double minz; 23 typedef point pointt; 24 pointt operator -(point a,point b) 25 { 26     return point(a.x-b.x,a.y-b.y); 27 } 28 int dcmp(double x) 29 { 30     if(fabs(x)<eps) return 0; 31     return x<0?-1:1; 32 } 33 double dis(point a) 34 { 35     return sqrt(a.x*a.x+a.y*a.y); 36 } 37 double cross(point a,point b) 38 { 39     return a.x*b.y-a.y*b.x; 40 } 41  42 double getarea(int n,point p[]) 43 { 44     int i; 45     double s = 0; 46     for(i = 1; i < n-1 ; i++) 47     s+=cross(p[i]-p[0],p[i+1]-p[0]); 48     return s/2; 49 } 50 //double cal(double r,point p[],int n) 51 //{ 52 //    int i,j; 53 //    int k = 1; 54 //    for(i = 1; i <= n; i++) 55 //    if(p[i].y<p[k].y)    k = i; 56 // 57 //    r = min(r,minz); 58 //    if(dcmp(r-p[k].y)<=0) return 0.0; 59 // 60 //    point p1,p2; 61 //    int g = 0; 62 //    for(i = 1; i < k; i++) 63 //    if(dcmp(p[i].y-r)>=0&&dcmp(p[i+1].y-r)<0) 64 //    { 65 //        p1.y = r; 66 //        double d = r-p[i+1].y; 67 //        p1.x = d*(p[i].x-p[i+1].x)/(p[i].y-p[i+1].y)+p[i+1].x; 68 //        break; 69 //    } 70 //   // cout<<p1.x<<" "<<p1.y<<endl; 71 //    for(j = k ; j >= i+1; j--) 72 //    ch[++g] = p[j]; 73 //    ch[++g] = p1; 74 //    for(i = k+1 ; i <= n; i++) 75 //    if(dcmp(p[i-1].y-r)<0&&dcmp(p[i].y-r)>=0) 76 //    { 77 //        p2.y = r; 78 //        double d = r-p[i-1].y; 79 //        p2.x = d*(p[i].x-p[i-1].x)/(p[i].y-p[i-1].y)+p[i-1].x; 80 //        break; 81 //    } 82 //    ch[++g] = p2; 83 //    for(j = i-1 ; j > k; j--) 84 //    ch[++g] = p[j]; 85 // 86 //    return fabs(getarea(g,ch)); 87 //} 88 point intersect(point p1,point p2,point p3,point p4){ 89     point p; 90     double a1,b1,a2,b2,c1,c2,d; 91     a1=p1.y-p2.y; b1=p2.x-p1.x; c1=p1.x*p2.y-p2.x*p1.y; 92     a2=p3.y-p4.y; b2=p4.x-p3.x; c2=p3.x*p4.x-p4.x*p3.y; 93     d=a1*b2-a2*b1; 94     p.x=(-c1*b2+c2*b1)/d; 95     p.y=(-a1*c2+a2*c1)/d; 96     return p; 97 } 98 bool pan(point a,point b,double y){ 99     return dcmp(a.y-y)*dcmp(b.y-y)<=0;100 }101 double cal(double y,point P[],int n){102 103     int i,j,k;104    int tot=0;105     point a=point(0,y),b=point(1,y);106     for(i=1;i<n;i++){107         if(pan(P[i],P[i+1],y)){108             ch[tot++]=intersect(P[i],P[i+1],a,b);109             break;110         }111     }112     for(j=i+1;j<n;j++){113         ch[tot++]=P[j];114         if(pan(P[j],P[j+1],y)){115             ch[tot++]=intersect(P[j],P[j+1],a,b);116             break;117         }118     }119     double area=getarea(tot,ch);120     return area;121 }122 int main()123 {124     int t,i,a,n,m;125     cin>>t;126     while(t--)127     {128         scanf("%d",&a);129         scanf("%d",&n);130         minz = INF;131         for(i = 1; i <= n ;i++)132         {133             scanf("%lf%lf",&p[i].x,&p[i].y);134             minz = min(minz,p[i].y);135         }136         scanf("%d",&m);137         for(i = 1; i <= m ;i++)138         {139             scanf("%lf%lf",&q[i].x,&q[i].y);140             minz = min(minz,q[i].y);141         }142         double maxz = min(min(p[1].y,p[n].y),min(q[1].y,q[m].y));143         double lef = minz,rig = maxz,mid;144         while(fabs(rig-lef)>eps)145         {146             mid = (rig+lef)/2.0;147             double s1 = cal(mid,p,n),s2 = cal(mid,q,m);148             if(dcmp(s1+s2-a)>0)149             rig = mid;150             else lef = mid;151         }152         printf("%.3f\n",lef);153     }154     return 0;155 }