【bzoj1091】[SCOI2003]切割多边形

2015.06.24 15:05 Wed | 26次阅读 | 旧日oi | 固定链接 | 源码

Description

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

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

题解

暴力题,枚举割线的顺序然后割一下就行了。注意没有什么能预处理出来的东西……比如每个点离哪边近……
代码还不太好写……

我的程序

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
struct Point
{
    double x,y;
    Point(double _,double __):x(_),y(__){}
    Point(){}
    Point operator - (const Point &a)const{
        return Point(x-a.x,y-a.y);
    }
    Point operator + (const Point &a)const{
        return Point(x+a.x,y+a.y);
    }
    Point operator * (double a)const{
        return Point(x*a,y*a);
    }
}p[10];
struct Line
{
    Point x,v;
    double alpha;
    Line(Point _,Point __):x(_),v(__){
        alpha=atan2(v.y,v.x);
    }
    Line(){}
}line[50];
int a[10];
double dis[10][2];
double n,m;
int P,cnt=3;
double getdis(Point a,Point b)
{
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
double cross(Point &a,Point &b)
{
    return a.x*b.y-a.y*b.x;
}
Point get_intersection(Line a,Line b)
{
    if((a.v.x==0&&b.v.x==0)||(a.v.y==0&&b.v.y==0)) return Point(n+1,m+1);
    Point u=a.x-b.x;
    double tmp=cross(b.v,u)/cross(a.v,b.v);
    return a.x+a.v*tmp;
}
bool inrange(Point tmp)
{
    if(tmp.x<0||tmp.x>n) return 0;
    if(tmp.y<0||tmp.y>m) return 0;
    return 1; 
}
double get_dis(Line a)
{
    Point tmp,b=a.x-a.v;
    double minn=233333333;
    for(int i=0;i<=cnt;i++)
    {
        tmp=get_intersection(a,line[i]);
        if(inrange(tmp))
        if((tmp.x<=a.x.x&&a.x.x<=b.x)||(tmp.x>=a.x.x&&a.x.x>=b.x))
        if((tmp.y<=a.x.y&&a.x.y<=b.y)||(tmp.y>=a.x.y&&a.x.y>=b.y))
        minn=min(minn,getdis(tmp,a.x));
    }
    return minn;
}
bool vis[10];
double cir;
double calc()
{
    memset(vis,0,sizeof(vis));
    double ret=cir;
    for(int i=1;i<=P;i++)
    {
        if(!vis[a[i]]) ret+=get_dis(Line(p[a[i]],p[a[i]]-p[a[i]+1]));
        if(!vis[a[i]%P+1]) ret+=get_dis(Line(p[a[i]+1],p[a[i]+1]-p[a[i]]));
        vis[a[i]]=vis[a[i]%P+1]=1;
        line[++cnt]=Line(p[a[i]],p[a[i]+1]-p[a[i]]);
    }
    return ret;
}
int main()
{
    cin>>n>>m>>P;
    line[0]=Line(Point(0,0),Point(0,m)-Point(0,0));
    line[1]=Line(Point(0,0),Point(n,0)-Point(0,0));
    line[2]=Line(Point(n,0),Point(n,m)-Point(n,0));
    line[3]=Line(Point(0,m),Point(n,m)-Point(0,m));
    for(int i=1;i<=P;i++) 
    {
        scanf("%lf%lf",&p[i].x,&p[i].y);
        a[i]=i;
    }
    p[P+1]=p[1];
    for(int i=1;i<=P;i++) cir+=getdis(p[i],p[i+1]);
    double ans=233333333;
    do{
        cnt=3;
        ans=min(ans,calc());
    }while(next_permutation(a+1,a+P+1));
    printf("%.3lf\n",ans);
}```