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

ydc的博客

 
 
 

日志

 
 

bzoj 1035(zjoi 2008) risk 平面区域练习题  

2013-02-26 18:27:39|  分类: bzoj |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

平面区域这个东西我最早是在LRJ的白书上看到的

书上只有非常简单的几行,以至于我连这个算法要我干什么我都不知道

还好冬令营时qq大神讲了,令我豁然开朗

回宾馆写,由于宾馆的网速以及若干偶然因素让我极其不爽,最后就没写了

然后冬令营就考了……

 

第二次想写是冬令营回来开课后的几天

结果很多东西都没想清,最后写不下去了

 

昨天鼓起勇气开始写

还翻出了冬令营时的讲义

如果没写出来的话,不知又要拖到什么时候去了

还好写出来了

 

我的实现异常暴力,并且pascal党与C党可以直接无视了……

用了各种STL

不过也是,比如冬令营上说,给某个点出发的线段排序

第二次写的时候纠结啊,某个点出发的线段,还要排序。当时我是想用数组就实现这些过程的,可惜代码能力太弱了

所以这次就果断STL了,用个map把点和线段都存起来再对每个点建一个vector然后就可以快排了…………

 

求平面区域的大致方法

平面区域这个东西,就是说一张平面图中有若干个域(也就是若干个块块),我要你用一个东西把这些块块全都抠出来,然后存下来

方法是这样的

把每条边拆成两条有向边,比如(a,b)写成a->b和b->a(并且为了方便实现,我们让两条互为反边关系的边的编号分别是i,i^1)

把每个点连的直线按顺时针排序(这一部分用vector和map会觉得非常爽)

然后类似于种子染色样的实现:枚举一条没有被选择过的边标记一下,选择以这条边终点为起点的、按顺时针排好序后反边的下一条边(这句话有点绕口),然后把新边标记并从新边开始继续做上面那个操作,一直到走与最开始的这条边为止(注意一定要是边)

寻找反边后的下一条边可以用个数组来记,那么为了方便实现,我果断又开了一个map

c++无敌啊!!

最后会得到外轮廓(比如一个田字格,正确答案是四个口字,但是这么做可能得到四个口字加一个田字,而田字不应该属于要求的),判断的方法是如果有向面积为负数就不加进去(有向面积就与顺时针和逆时针有关了,这样就能把田字砍掉)

 

那么讲下这道题吧

把平面区域求出来

然后按面积快排,这样就能保证一定是后面包含前面了

我们可以让某条边与他的反边是i与i^1的关系

然后把某条边属于哪个平面区域都记下来

然后把军队与国家一一配对,方法是枚举军队,从前往后枚举国家,如果点在多边形内就更新并break。如果有包含关系怎么办呢?按面积快排就是为了解决这个问题,只要a的面积小于b的面积,a就不可能包含b,那么我们枚举到的第一个自然就是答案

判(i,j)相邻的话分两种情况

一个是i的某条边的反边属于j

另一个是包含,刚开始我就乱YY结果YY错了,果断WA了一个点然后发现不知道如何处理。于是搜题解……其实是这么做的:

如果某个多边形,存在某条边的反边是外轮廓即不属于任何其他边,那么最小的包含它的多边形就与他相邻。注意包含的判断方式只要看这个军队在不在那个多边形内即可判断包含了,还有前面那个条件至关重要否则会误判

 

其实代码也不算很长,这题也就是那么回事吧

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#include<map>
#include<ctime>
#define MAXN 610
#define MAXM 8010
using namespace std;
typedef long long LL;
int pos[MAXM],tot=1;
struct Point
{
    int x,y;
    void Read(){  scanf("%d %d",&x,&y);  }
    Point() {}
    Point(int x,int 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 bool operator < (const Point &a,const Point &b){  return a.x<b.x||(a.x==b.x&&a.y<b.y);  }
    friend bool operator != (const Point &a,const Point &b){  return a.x!=b.x||a.y!=b.y;  }
    friend bool operator == (const Point &a,const Point &b){  return a.x==b.x&&a.y==b.y;  }
}army[MAXN];
typedef Point Vector;
LL Cross(const Vector &a,const Vector &b){  return a.x*b.y-a.y*b.x;  }
map<Point,int>hash1;
struct Seg
{
    Point l,r;
    Vector v;
    double rad;
    Seg() {}
    Seg(const Point &l,const Point &r): l(l),r(r) {  v=r-l,rad=atan2(v.y,v.x);  }
    friend bool operator < (const Seg &a,const Seg &b){  return a.l<b.l||(a.l==b.l&&a.r<b.r);  }
    friend bool operator != (const Seg &a,const Seg &b){  return a.l!=b.l||a.r!=b.r;  }
    friend bool operator == (const Seg &a,const Seg &b){  return a.l==b.l&&a.r==b.r;  }
}L[MAXM];
map<Seg,int>hash2;
vector<Seg>p[MAXM];
vector<int>ans[MAXN];
bool Inter(const Seg &a,const Seg &b){  return Cross(a.r-a.l,b.l-a.l)*Cross(a.r-a.l,b.r-a.l)<=0&&Cross(b.r-b.l,a.l-b.l)*Cross(b.r-b.l,a.r-b.l)<=0;  }
struct Polygon
{
    vector<Point>p;
    vector<int>edge;
    int area2,num;
    void work()
    {
        edge.clear();
        for(int i=0;i<p.size()-1;i++)
            edge.push_back(hash2[Seg(p[i],p[i+1])]);
        edge.push_back(hash2[Seg(p[p.size()-1],p[0])]);
    }
    void calc_Area()
    {
        area2=0;
        for(int i=1;i<p.size()-1;i++)
            area2-=Cross(p[i]-p[0],p[i+1]-p[0]);
    }
    bool In(const Point &P)
    {
        bool flag=false;
        Seg Ray=Seg(Point(-10001,P.y),P);
        for(int i=0;i<p.size();i++)
        {
            Seg now=Seg(p[i],p[(i+1)%p.size()]);
            if(P.y!=min(now.l.y,now.r.y))
                if(Inter(now,Ray))
                    flag^=1;
        }
        return flag;
    }
    friend bool operator < (const Polygon &a,const Polygon &b){  return a.area2<b.area2;  }
}State[MAXN];
int n,m;
bool cmp(const Seg &a,const Seg &b){  return a.rad<b.rad;  }
void read()
{
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++)
        army[i].Read();
    Point a,b;
    int k=0,x,y;
    for(int i=1;i<=m;i++)
    {
        a.Read(),b.Read();
        if(!hash1.count(a))  hash1[a]=++k;
        if(!hash1.count(b))  hash1[b]=++k;
        x=hash1[a],y=hash1[b];
        L[++tot]=Seg(a,b),hash2[L[tot]]=tot,p[x].push_back(L[tot]);
        L[++tot]=Seg(b,a),hash2[L[tot]]=tot,p[y].push_back(L[tot]);
    }
    for(int i=1;i<=k;i++)
    {
        sort(p[i].begin(),p[i].end(),cmp);
        for(int j=0;j<p[i].size();j++)
            pos[hash2[p[i][j]]]=j;
    }
}
void Find_Polygon()
{
    static bool use[MAXM];
    Polygon country;
    Seg Seg1,Seg2;
    int s=0;
    for(int i=2;i<=tot;i++)
        if(use[i]==false)
        {
            use[i]=true,Seg1=L[i],Seg2=Seg(L[i].r,L[i].l);
            country.p.clear();
            country.p.push_back(Seg1.l);
            while(1)
            {
                int next=hash1[Seg2.l],k=hash2[Seg2];
                Seg1=p[next][(pos[k]+1)%p[next].size()];
                Seg2=Seg(Seg1.r,Seg1.l);
                if(Seg1==L[i])  break;
                country.p.push_back(Seg1.l),use[hash2[Seg1]]=true;
            }
            country.calc_Area();
            if(country.area2>0)  State[++s]=country;
        }
    for(int i=1;i<=s;i++)
        State[i].work();
}
void Get_num()
{
    sort(State+1,State+n+1);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(State[j].In(army[i]))
            {
                State[j].num=i;
                break;
            }
}
void Get_ans()
{
    static int pos[MAXM],father[MAXN];
    for(int i=1;i<=tot;i++)
        pos[i]=0;
    for(int i=1;i<=n;i++)
        father[i]=0;
    for(int i=1;i<=n;i++)
        for(int j=0;j<State[i].p.size();j++)
            pos[State[i].edge[j]]=i;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(j!=i)
            {
                bool mark=false;
                int x=State[i].num,y=State[j].num;
                for(int k=0;k<State[i].p.size()&&!mark;k++)
                    if(pos[State[i].edge[k]^1]==j)
                        mark=true,ans[x].push_back(y);
                if(!mark&&!father[y])
                {
                    bool mark=false;
                    for(int k=0;k<State[j].p.size()&&!mark;k++)
                        if(pos[State[j].edge[k]^1]==0)
                            mark=true;
                    if(mark&&State[i].In(army[State[j].num]))
                        father[y]=x,ans[x].push_back(y),ans[y].push_back(x);
                }
            }
}
void print()
{
    for(int i=1;i<=n;i++)
    {
        printf("%d%c",ans[i].size(),ans[i].size()==0?'\n':' ');
        sort(ans[i].begin(),ans[i].end());
        for(int j=0;j<ans[i].size();j++)
            printf("%d%c",ans[i][j],j<ans[i].size()-1?' ':'\n');
    }
}
int main()
{
    read();
    Find_Polygon();
    Get_num();
    Get_ans();
    print();
    return 0;
}


  评论这张
 
阅读(642)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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