1 #include <iostream> 2 #include <stdio.h> 3 #include <string.h> 4 #include <stdlib.h> 5 #include <algorithm> 6 using namespace std; 7 typedef long long ll; 8 const int maxn = 1e3+10; 9 const double INF = 0x3f3f3f3f; 10 const double eps = 1e-10; 11 const double PI = acos(-1.0); 12 int dcmp(double k) {return k<-eps?-1:k>eps?1:0;} 13 double sqr(double x) {return x*x;} 14 double mysqrt(double n) {return sqrt(max(0.0,n));} 15 16 struct point{ 17 double x,y; 18 point (double x=0, double y=0):x(x),y(y){} 19 }; 20 21 typedef point Vector; 22 23 point res[maxn]; 24 double r; 25 int n; 26 27 Vector operator +(Vector A,Vector B) {return Vector(A.x+B.x,A.y+B.y); } 28 Vector operator -(Vector A,Vector B) {return Vector(A.x-B.x,A.y-B.y); } 29 Vector operator *(Vector A,double p) {return Vector(A.x*p,A.y*p); } 30 Vector operator /(Vector A,double p) {return Vector(A.x/p,A.y/p); } 31 double dot(const point &a, const point &b) {return a.x*b.x+a.y*b.y;} 32 double cross(const point &a, const point &b) {return a.x*b.y-a.y*b.x;} 33 double abs(const point &o) {return sqrt(dot(o,o));} 34 35 point crosspt(const point &a, const point &b, const point &p, const point &q) 36 { 37 double a1 = cross(b-a,p-a); 38 double a2 = cross(b-a,q-a); 39 return (p*a2-q*a1)/(a2-a1); 40 } 41 42 void circle_cross_line(point a,point b,point o,double r,point ret[],int &num) 43 { 44 double x0 = o.x,y0 = o.y; 45 double x1 = a.x,y1 = a.y; 46 double x2 = b.x,y2 = b.y; 47 double dx = x2-x1, dy = y2-y1; 48 double A = dx*dx+dy*dy; 49 double B = 2*dx*(x1-x0)+2*dy*(y1-y0); 50 double C = sqr(x1-x0) + sqr(y1-y0) -sqr(r); 51 double delta = B*B-4*A*C; 52 num = 0; 53 if(dcmp(delta)>=0) 54 { 55 double t1 = (-B-mysqrt(delta))/(2*A); 56 double t2 = (-B+mysqrt(delta))/(2*A); 57 if(dcmp(t1-1)<=0 && dcmp(t1)>=0) 58 { 59 ret[num++] = point(x1+t1*dx,y1+t1*dy); 60 } 61 if(dcmp(t2-1)<=0 && dcmp(t2)>=0) 62 { 63 ret[num++] = point(x1+t2*dx,y1+t2*dy); 64 } 65 } 66 } 67 68 double sector_area(const point &a, const point &b) 69 { 70 double theta = atan2(a.y,a.x)-atan2(b.y,b.x); 71 while(theta<=0) theta += 2*PI; 72 while(theta>2*PI) theta -= 2*PI; 73 theta = min(theta,2*PI-theta); 74 return r*r*theta/2; 75 } 76 77 double calc(const point &a, const point &b) 78 { 79 point p[2]; 80 int num=0; 81 int ina = dcmp(abs(a)-r)<0; 82 int inb = dcmp(abs(b)-r)<0; 83 if(ina) 84 { 85 if(inb) 86 { 87 return fabs(cross(a,b))/2.0; 88 } 89 else 90 { 91 circle_cross_line(a,b,point(0,0),r,p,num); 92 return sector_area(b,p[0])+fabs(cross(a,p[0]))/2.0; 93 } 94 } 95 else 96 { 97 if(inb) 98 { 99 circle_cross_line(a,b,point(0,0),r,p,num); 100 return sector_area(p[0],a)+fabs(cross(p[0],b))/2.0; 101 } 102 else 103 { 104 circle_cross_line(a,b,point(0,0),r,p,num); 105 if(num==2) 106 { 107 return sector_area(a,p[0])+sector_area(p[1],b)+fabs(cross(p[0],p[1])) / 2.0; 108 } 109 else 110 { 111 return sector_area(a,b); 112 } 113 } 114 } 115 } 116 117 //计算多边形和圆相交的面积,半径为r,圆心为圆点,n边形,n个点顺序存在ret[0~n-1]中,ret[n]=ret[0] 118 double area() 119 { 120 double ret = 0; 121 for(int i=0;i<n;i++) 122 { 123 int sgn = dcmp(cross(res[i],res[i+1])); 124 ret += sgn*calc(res[i],res[i+1]); 125 // if(sgn>0) ret += calc(res[i],res[i+1]); 126 // else ret -= calc(res[i],res[i+1]); 127 } 128 return fabs(ret); 129 } 130 131 point p[maxn]; 132 int m; 133 double P,Q; 134 double allArea;//多边形面积 135 136 //顺时针逆时针均可 137 double Area() 138 { 139 double ans = 0.0; 140 for(int i=0;i<n;i++) 141 { 142 ans = ans + cross(p[i+1],p[i]); 143 } 144 return fabs(ans/2); 145 } 146 147 148 int main() 149 { 150 scanf("%d",&n); 151 for(int i=0;i<n;i++) 152 { 153 double x,y; 154 scanf("%lf %lf",&x,&y); 155 p[i] = point(x,y); 156 a[n-i-1] = point(x,y); 157 } 158 p[n].x=p[0].x,p[n].y=p[0].y; 159 160 allArea = Area(); 161 //printf("%.12f\n",allArea); 162 163 scanf("%d",&m); 164 for(int i=1;i<=m;i++) 165 { 166 double x,y; 167 scanf("%lf %lf %lf %lf",&x,&y,&P,&Q); 168 169 point tmp = point(x,y); 170 double goal = (1.-P/Q)*allArea; 171 172 for(int i=0;i<=n;i++) 173 { 174 res[i] = p[i]-tmp; 175 } 176 177 double left = 0,right = 1e5; 178 while(right-left>eps) 179 { 180 double mid = (right+left)*.5; 181 r = mid; 182 183 double Area = area(); 184 if(Area<goal) left = mid; 185 else right = mid; 186 } 187 printf("%.12f\n",right); 188 } 189 }