Description

有一个凸p边形(p<=8)，我们希望通过切割得到它。一开始的时候，你有一个n*m的矩形，即它的四角的坐标分别为(0,0), (0,m), (n,0), (n,m)。每次你可以选择一条直线把当前图形切割成两部分，保留其中一个部分（另一部分扔掉）切割线的长度为此直线在多边形内部的部分的长度。求出最短的切割线总长度。下面是一个例子。我们需要得到中间的多边形。

分别沿着直线1，2，3，4进行切割即可，得到中间的四边形。

Input

第一行有两个整数n, m(0 < n,m < 500)，第二行为一个整数p(3<=p<=8)。以下p行每行为两个整数x, y(0 < x < n, 0 < y < m)，为按顺时针给出的各顶点坐标。数据保证多边形的是凸的，无三点共线。输入数据无错误。

Output

仅一行，为最短切割线的总长度，四舍五入到小数点后3位。允许有0.001的误差。<??http://www.2cto.com/kf/ware/vc/" target="_blank" class="keylink">vcD4KCjxoMj5TYW1wbGUgSW5wdXQ8L2gyPgoKMTAwIDEwMDxicj4KNDxicj4KODAgODA8YnI+CjcwIDMwPGJyPgoyMCAyMDxicj4KMjAgODAKPGgyPlNhbXBsZSBPdXRwdXQ8L2gyPgoKMzEyLjU3NQo8aDI+SElOVDwvaDI+Cgo8cD48L3A+CjxwPtH5wP221NOm09rNvNbQuPiz9rXEwP3X06GjPC9wPgo8cD48L3A+Cgo8aDI+U291cmNlPC9oMj4KCjxwPjwvcD4KCjxicj4KPHA+PC9wPgo8cD48YnI+CjwvcD4KPHA+1rG907DRtuCx39DOyeyzpLPJMrXjtrzU2r7Y0M7Jz7XEz9+2zqOs1eLR+bXEu7DDv7TOyKHKsbDR1q7HsLXEz9+2zrju0rvPwqGjPC9wPgo8cD7XotLiyeyzpMqxsaPWpM/ywb+3vc/yPC9wPgo8cD48YnI+CjwvcD4KPHA+PGJyPgo8L3A+CjxwPjxwcmUgY2xhc3M9"brush:java;">#include #include #include #include #include #include #include #include #include using namespace std; #define For(i,n) for(int i=1;i<=n;i++) #define Fork(i,k,n) for(int i=k;i<=n;i++) #define Rep(i,n) for(int i=0;i =0;i--) #define Forp(x) for(int p=pre[x];p;p=next[p]) #define Lson (x<<1) #define Rson ((x<<1)+1) #define MEM(a) memset(a,0,sizeof(a)); #define MEMI(a) memset(a,127,sizeof(a)); #define MEMi(a) memset(a,128,sizeof(a)); #define INF (2139062143) #define F (1000000007) #define MP make_pair #define MAXP (500+10) #define MAXN (500+10) #define MAXM (500+10) #define eps (1e-6) long long mul(long long a,long long b){return (a*b)%F;} long long add(long long a,long long b){return (a+b)%F;} long long sub(long long a,long long b){return (a-b+(a-b)/F*F+F)%F;} typedef long long ll; int n,m,p; double sqr(double x){return x*x;} int dcmp(double a,double b=0){if (fabs(a-b)<=eps) return 0;else if (a >(istream& cin,P &a){cin>>a.x>>a.y;return cin;} friend ostream& operator<<(ostream& cout,P &a){cout< =0; } void print(){cout< =0&&dcmp(a.x,n)<=0&&dcmp(a.y)>=0&&dcmp(a.y,m)<=0);} L through_rec_line(L l) { int siz=0;P st[3]; if (dcmp(l.v.x)==0) return L(P(l.p.x,l.v.y>0?0:m),V(0,(l.v.y>0?1:-1)*m)); if (dcmp(l.v.y)==0) return L(P(l.v.x>0?0:n,l.p.y),V((l.v.x>0?1:-1)*n,0)); //至此保证不平行坐标系 Rep(i,4) { if (parallel(lrec[i],l)) continue; st[++siz]=intersect(lrec[i],l); if (!inrec(st[siz])) siz--; if (siz==2) { if (st[1]==st[2]) siz--; else { V a=V(st[1],st[2]); if (dcmp(a^l.v)<0) return L(st[2],V(st[2],st[1])); return L(st[1],a); } } } } bool b[MAXP]={0}; double ans=1e300; int cut_list[MAXN]; void dfs(double tot,int siz) { if (tot>ans) return; if (siz==p) { // Rep(i,siz) cout< >n>>m>>p; ForD(i,p) cin>>a[i];memcpy(a+p+1,a+1,sizeof(P)*p); For(i,p) l[i]=L(a[i],V(a[i],a[i+1]));memcpy(l+p+1,l+1,sizeof(L)*p); lrec[0]=L(P(0,0),V(n,0)),lrec[1]=L(P(n,0),V(0,m)),lrec[2]=L(P(n,m),V(-n,0)),lrec[3]=L(P(0,m),V(0,-m)); For(i,p) l[i]=through_rec_line(l[i]); // For(i,p) l[i].print(); dfs(0,0); printf("%.3lf\n",ans); return 0; }