#include <stdio.h> #include <math.h> #include <algorithm> using namespace std; const double eps=1e-8; double h,ans,cake; struct point { double x,y; point (){} point (double x,double y):x(x),y(y){} void get(){scanf("%lf%lf",&x,&y);} }; struct poly{ point p[21]; int n; void get(){for(int i=0;i<n;i++)p[i].get();p[n]=p[0];} }sg; int dcmp(double x){ return (x>eps)-(x<-eps); } double cross(point o,point p,point q){ return (p.x-o.x)*(q.y-o.y)-(p.y-o.y)*(q.x-o.x); } point lineinter(point a,point b,point c,point d){ double u=cross(a,b,c),v=cross(b,a,d); return point((c.x*v+d.x*u)/(u+v),(c.y*v+d.y*u)/(u+v)); } double dis(point a,point b){ return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); } void push(point a,point b,point &c,point &d){ double x=a.y-b.y,y=b.x-a.x,t=h/dis(a,b); c=point(a.x+x*t,a.y+y*t); d=point(b.x+x*t,b.y+y*t); } void cut(point a,point b,poly tg,poly &g){ push(a,b,a,b); g.n=0; for(int i=0;i<tg.n;i++){ int u=dcmp(cross(a,b,tg.p[i])),v=dcmp(cross(a,b,tg.p[i+1])); if(u>=0)g.p[g.n++]=tg.p[i]; if(u*v<0) g.p[g.n++]=lineinter(a,b,tg.p[i],tg.p[i+1]); } g.p[g.n]=g.p[0]; } double area(poly g){ double sum=0; for(int i=2;i<g.n;i++) sum+=cross(g.p[0],g.p[i-1],g.p[i]); return 0.5*sum; } void dfs(int i,int step,poly g){ if(step+i<sg.n)dfs(i+1,step,g); cut(sg.p[i],sg.p[i+1],g,g); if(step==1)ans=max(ans,cake-area(g)); else dfs(i+1,step-1,g); } int main(){ int k; while(scanf("%d%d%lf",&sg.n,&k,&h),sg.n||k||h){ sg.get(); cake=area(sg); ans=0; k=min(k,sg.n); if(k&&h)dfs(0,k,sg); printf("%.2lf\n",ans); } return 0; }
|