BZOJ 1091([SCOI2003]分割多边形-分割直线)

1091: [SCOI2003]分割多边形

Time Limit: 1 Sec Memory Limit: 162 MB

Submit: 223 Solved: 82

[Submit][

id=1091" style="color:blue; text-decoration:none">Status]

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的误差。

Sample Input

100 100

4

80 80

70 30

20 20

20 80

Sample Output

312.575

HINT

例子相应于图中给出的例子。

Source

直接把多边形伸长成2点都在矩形上的线段，这种话每次取时把之前的线段割一下。

注意伸长时保证向量方向

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<algorithm>

#include<functional>

#include<iostream>

#include<cmath>

#include<cctype>

#include<ctime>

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<n;i++)

#define ForD(i,n) for(int i=n;i;i--)

#define RepD(i,n) for(int i=n;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<b) return -1;return 1;}

struct P

{

    double x,y;

    P(){}

    P(double _x,double _y):x(_x),y(_y){}

    friend istream& operator>>(istream& cin,P &a){cin>>a.x>>a.y;return cin;}

    friend ostream& operator<<(ostream& cout,P &a){cout<<a.x<<' '<<a.y;return cout;}

    friend bool operator==(P a,P b){return dcmp(a.x,b.x)==0&&dcmp(a.y,b.y)==0;    }

}a[MAXP];

struct V

{

    double x,y;

    V(){}

    V(double _x,double _y):x(_x),y(_y){}

    V(P a,P b):x(b.x-a.x),y(b.y-a.y){}

    friend V operator*(double a,V b){return V(a*b.x,a*b.y);}

    friend V operator-(P a,P b){return V(b.x-a.x,b.y-a.y); }

    friend double operator*(V a,V b){return a.x*b.y-a.y*b.x;}

    friend double operator^(V a,V b){return a.x*b.x+a.y*b.y;}

    friend P operator+(P a,V b){return P(a.x+b.x,a.y+b.y);    }

    friend double dis2(V a){return sqr(a.x)+sqr(a.y);    }

};

struct L

{

    P p;

    V v;

    L(){}

    L(P _A,V _B):p(_A),v(_B){}

    friend bool parallel(L a,L b) {return (dcmp(a.v.x*b.v.y,a.v.y*b.v.x))==0;}

    friend P intersect(L a,L b) //直线交点

    {

        V &v=a.v,&w=b.v,u=V(b.p,a.p);

        double t=(w*u)/(v*w);

        P c=a.p+t*v; return c;

    }

    friend bool inleft(P a,L b){return dcmp(b.v*V(b.p,a))>=0;    }

    void print(){cout<<p.x<<' '<<p.y<<' '<<v.x<<' '<<v.y<<endl;    }

}l[MAXP],lrec[4];

bool inrec(P a){return (dcmp(a.x)>=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<<cut_list[i]<<' ';printf("%.3lf\n",ans);

        ans=min(ans,tot);

        return;

    }

    /*

    if (siz==2)

    {

        if (cut_list[0]==2&&cut_list[1]==1)

        {

            cout<<' ';

        }

    }*/

    For(i,p)

        if (!b[i])

        {

            L x=through_rec_line(l[i]);

            For(j,p)

                if (!parallel(l[j],x)&&b[j])

                {

                    P p=intersect(x,l[j]);

                    if (dcmp(V(p,x.p)^V(p,x.p+x.v))<0)

                    {

                        if (!inleft(x.p,l[j])) x=L(p,V(p,x.p+x.v));

                        else if (!inleft(x.p+x.v,l[j])) x=L(x.p,V(x.p,p));

                    }

                }

            b[i]=1;

            cut_list[siz]=i;

        /*

            Rep(j,siz) printf("\t");

            cout<<i<<endl;

            printf("%.3lf\n",tot+sqrt(dis2(x.v)));

          */

            dfs(tot+sqrt(dis2(x.v)),siz+1);

            b[i]=0;

        }

}

int main()

{

//  freopen("bzoj1091.in","r",stdin);

//  freopen("bzoj1091.out","w",stdout);

    cin>>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;

}

巴特西