The small sawmill in Mission, British Columbia, has developed a brand new way of packaging boards for drying. By xating the boards in special moulds, the board can dry efficiently in a drying room. Space is an issue though. The boards cannot be too close, because then the drying will be too slow. On the other hand, one wants to use the drying room efficiently. Looking at it from a 2-D perspective, your task is to calculate the fraction between the space occupied by the boards to the total space occupied by the mould. Now, the mould is surrounded by an aluminium frame of negligible thickness, following the hull of the boards’ corners tightly. The space occupied by the mould would thus be the interior of the frame. Input On the rst line of input there is one integer, N 50, giving the number of test cases (moulds) in the input. After this line, N test cases follow. Each test case starts with a line containing one integer n , 1
#include<cstdio>#include<cstring>#include<cmath>#include<algorithm>using namespace std;const double eps=1e-8,pi=acos(-1);int cmp(double x){ if (x>eps) return 1; if (fabs(x)<eps) return 0; return -1;}struct vector{ double x,y; bool Operator < (const vector &v) const { return cmp(x-v.x)==-1||(cmp(x-v.x)==0&&cmp(y-v.y)==-1); } bool operator == (const vector &v) const { return cmp(x-v.x)==0&&cmp(y-v.y)==0; } vector operator + (const vector &v) const { return (vector){x+v.x,y+v.y}; } vector operator - (const vector &v) const { return (vector){x-v.x,y-v.y}; } vector operator * (const double &k) const { return (vector){x*k,y*k}; } vector operator / (const double &k) const { return (vector){x/k,y/k}; }};typedef vector point;double cross(vector v1,vector v2){ return v1.x*v2.y-v1.y*v2.x;}vector rot(vector v,double r){ return (vector){v.x*cos(r)-v.y*sin(r),v.y*cos(r)+v.x*sin(r)};}point a[2500],f[2500];int n;double solve(){ double x,y,w,h,r,sum=0,s=0,x1,y1,x2,y2; int m,mm; scanf("%d",&n); for (int i=1;i<=n;i++) { scanf("%lf%lf%lf%lf%lf",&x,&y,&w,&h,&r); point o=(point){x,y}; r=-r*pi/180; sum+=w*h; a[i*4-4]=o+rot((vector){w/2,h/2},r); a[i*4-3]=o+rot((vector){w/2,-h/2},r); a[i*4-2]=o+rot((vector){-w/2,h/2},r); a[i*4-1]=o+rot((vector){-w/2,-h/2},r); } n*=4; sort(a,a+n); n=unique(a,a+n)-a; m=0; for (int i=0;i<n;i++) { while (m>=2&&cmp(cross(f[m-1]-f[m-2],a[i]-f[m-2]))==-1) m--; f[m++]=a[i]; } mm=m; for (int i=n-2;i>=0;i--) { while (m>mm&&cmp(cross(f[m-1]-f[m-2],a[i]-f[m-2]))==-1) m--; f[m++]=a[i]; } for (int i=1;i<m-2;i++) s+=cross(f[i]-f[0],f[i+1]-f[0]); s/=2; return sum/s;}int main(){ int T; scanf("%d",&T); while (T--) PRintf("%.1f %/n",solve()*100);}新闻热点
疑难解答
