注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

ydc的博客

 
 
 

日志

 
 

bzoj 1020  

2013-02-04 21:22:29|  分类: bzoj |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

正解应该是二分一个答案,然后把小岛按照答案扩大之后看是否新的多边形并能否覆盖航线。但这样子做过于麻烦!!

于是就有了莫涛的论文:《迭代思想的应用》

由于我昨天找这篇论文找了好久,为了方便大家,我就不在此打止,而是把方法讲一遍吧,希望能节省大家找资料的时间。

首先,在我看来,这个看似高深莫测的算法,其本质就是————搜索加剪枝!(好囧)

一个点一个点的搜肯定会超时吧。

我们就要一个可行性剪枝。

对于一条线段,取左端点的最近点p1,右端点的最近点p2,很显然在线段上的点,与p1距离会越来越大,与p2距离会越来越小,所以就可以二分一个答案p,使dis(p,p1)与dis(p,p2)最接近。

于是就到剪枝了:

r=max(dis(p,p1),dis(p,p2))

如果r<=当前的ans,那么这条线段就不需要了,可以删去。

因为:q是与p最近的点,那么dis(p,q)必定小于等于r,故<=当前的ans。而向左走dis(p,p2)增大所以r增大,同理向右走r也增大,所以这条线段找不到能更新答案的点。

所以算法如下:

用一个循环队列(或者queue)来记录线段,找到线段,求出p1,p2,二分答案求出p,删去线段。如果r>ans也即此线段可能有解,我们取线段中点mid,将(l,mid)与(mid,r)这两条线段插入队列。

由于很显然这样子会死循环,所以插入队列时,条件不应该是ans<r而应该是ans+0.005<r。

实在觉得这是搜索加剪枝啊,总担心会很慢……可我多虑了,因为交上去发现实际效率快的要死。

相比起二分答案,这个算法的编程复杂度非常优异,而时间复杂度经实践证明也是很快的。

膜拜莫涛大大大大神!

 

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define eps 1e-16
#define MAXN 30
#define MAXM 40
#define MAXQ 1000000
using namespace std;
int dcmp(double p)
{
    if(fabs(p)<eps)  return 0;
    return p>eps?1:-1;
}
int n,m;
double ans;
struct Point
{
    double x,y;
    Point() {}
    Point(double x,double y): x(x),y(y) {}
    friend Point operator + (const Point &a,const Point &b){  return Point(a.x+b.x,a.y+b.y);  }
    friend Point operator - (const Point &a,const Point &b){  return Point(a.x-b.x,a.y-b.y);  }
    friend Point operator * (const Point &a,double p){  return Point(a.x*p,a.y*p);  }
    friend Point operator / (const Point &a,double p){  return Point(a.x/p,a.y/p);  }
    friend bool operator == (const Point &a,const Point &b){  return !dcmp(a.x-b.x)&&!dcmp(a.y-b.y);  }
    void Read(){  scanf("%lf %lf",&x,&y);  }
}temp[MAXN];
typedef Point Vector;
double Dot(const Vector &a,const Vector &b){  return a.x*b.x+a.y*b.y;  }
double Len(const Vector &a){  return sqrt(Dot(a,a));  }
double Cross(const Vector &a,const Vector &b){  return a.x*b.y-a.y*b.x;  }
Vector Normal(const Vector &a){  return Vector(-a.y,a.x);  }
bool On(const Point &a,const Point &b,const Point &c){  return !dcmp(Cross(b-a,c-a))&&dcmp((a.x-b.x)*(a.x-c.x))<=0&&dcmp((a.y-b.y)*(a.y-c.y))<=0;  }
bool inter(const Point &a,const Point &b,const Point &c,const Point &d){  return dcmp(Cross(c-a,b-a)*Cross(d-a,b-a))<=0&&dcmp(Cross(a-c,d-c)*Cross(b-c,d-c))<=0;  }
Point getinter(const Point &a,const Vector &b,const Point &c,const Vector &d)
{
    Vector u=a-c;
    double t=Cross(d,u)/Cross(b,d);
    return a+b*t;
}
struct Seg
{
    Point a,b;
    Seg() {}
    Seg(const Point &a,const Point &b): a(a),b(b) {}
}queue[1000010];
struct Polygon
{
    Point p[MAXM];
    int tot;
    bool In(Point &point)
    {
        int total=0;
        for(int i=1;i<=tot;i++)
            if(On(point,p[i],p[i%tot+1]))
                return true;
        Point Ray=Point(-10001,point.y+0.1);
        point.y+=0.1;
        for(int i=1;i<=tot;i++)
            total=total+inter(Ray,point,p[i],p[i%tot+1]);
        point.y-=0.1;
        return total&1;
    }
}island[MAXN];
struct near
{
    Point P;
    double dis;
    near() {}
    near(const Point &a,double b): P(a),dis(b) {}
};
near DISPS(const Point &a,const Point &b,const Point &c)
{
    if(b==c)  return near(b,Len(b-a));
    Vector v1=c-b,v2=a-b,v3=a-c;
    if(dcmp(Dot(v1,v2))<=0)  return near(b,Len(v2));
    if(dcmp(Dot(v1,v3))>=0)  return near(c,Len(v3));
    Vector v=Normal(b-c);
    Point ans=getinter(a,v,b,v1);
    return near(ans,Len(a-ans));
}
bool check(Point &p)
{
    for(int i=1;i<=n;i++)
        if(island[i].In(p))
            return true;
    return false;
}
near Find(Point &p)
{
    if(check(p))  return near(p,0);
    near ans1;
    ans1.dis=1<<30;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=island[i].tot;j++)
        {
            near get=DISPS(p,island[i].p[j],island[i].p[j%island[i].tot+1]);
            if(dcmp(ans1.dis-get.dis)>=0)  ans1=get;
        }
    ans=max(ans,ans1.dis);
    return ans1;
}
void read()
{
    scanf("%d %d",&n,&m);
    for(int i=1;i<=m;i++)
        temp[i].Read();
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&island[i].tot);
        for(int j=1;j<=island[i].tot;j++)
            island[i].p[j].Read();
    }
}
void search()
{
    int front=0,rear=0;
    for(int i=1;i<m;i++)
        queue[++rear]=Seg(temp[i],temp[i+1]),Find(temp[i]);
    Find(temp[m]);
    Seg head;
    while(front!=rear)
    {
        head=queue[front=front%MAXQ+1];
        Point p1=Find(head.a).P,p2=Find(head.b).P,l=head.a,r=head.b,mid=(l+r)/2;
        while(Len(r-l)>1e-4)
        {
            Point mid=(r+l)/2;
            if(Len(mid-p1)<Len(mid-p2))  l=mid;
            else r=mid;
        }
        double nowans=max(Len(l-p1),Len(l-p2));
        Find(l);
        if(ans+0.005<nowans)  queue[rear=rear%MAXQ+1]=Seg(head.a,mid),queue[rear=rear%MAXQ+1]=Seg(mid,head.b);
    }
}
int main()
{
    read();
    search();
    printf("%.2lf\n",ans);
    return 0;
}

 


  评论这张
 
阅读(1218)| 评论(8)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017