欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

2020 年百度之星·程序设计大赛 - 测试赛 度度熊保护村庄 计算几何(叉积)+floyd(最小环)

程序员文章站 2022-07-03 17:56:55
2020 年百度之星·程序设计大赛 - 测试赛 度度熊保护村庄 计算几何(叉积)+floyd(最小环)Problem Description哗啦啦村袭击了喵哈哈村!度度熊为了拯救喵哈哈村,带着自己的伙伴去救援喵哈哈村去了!度度熊与伙伴们很快的就过来占据了喵哈哈村的各个军事要地,牢牢的守住了喵哈哈村。但是度度熊发现,这是一场旷日持久的战斗,所以度度熊决定要以逸待劳,保存尽量多的体力,去迎战哗啦啦村的战士。于是度度熊决定派尽量多的人去休息,但是同时也不能松懈对喵哈哈村的保护。换句话而...

2020 年百度之星·程序设计大赛 - 测试赛 度度熊保护村庄 计算几何(叉积)+floyd(最小环)

Problem Description

哗啦啦村袭击了喵哈哈村!

度度熊为了拯救喵哈哈村,带着自己的伙伴去救援喵哈哈村去了!度度熊与伙伴们很快的就过来占据了喵哈哈村的各个军事要地,牢牢的守住了喵哈哈村。

但是度度熊发现,这是一场旷日持久的战斗,所以度度熊决定要以逸待劳,保存尽量多的体力,去迎战哗啦啦村的战士。

于是度度熊决定派尽量多的人去休息,但是同时也不能松懈对喵哈哈村的保护。

换句话而言,度度熊希望尽量多的人休息,而且存在一个包围圈由剩下的人组成,且能够恰好的包围住喵哈哈村的所有住房(包括边界)。

请问最多能让多少个人休息呢?

Input

本题包含若干组测试数据。

第一行一个整数n,表示喵哈哈村的住房数量。

接下来n行,每行两个整数(x1[i],y1[i]),表示喵哈哈村的住房坐标。

第n+1行一个整数m,表示度度熊的士兵数量。

接下来m行,每行两个整数(x2[i],y2[i]),表示度度熊伙伴的坐标。

满足:

1<=n,m<=500

-10000<=x1[i],x2[i],y1[i],y2[i]<=10000

Output

请输出最多的人员休息的数目。

如果无法保护整个村庄的话,输出"ToT"

Sample Input

2
1 1
2 2
4
0 0
0 4
4 2
4 0
1
1 1
2
0 0
0 1

Sample Output

1
ToT

Solution

看完题目后,第一个反应就是这题要求凸包,以前也遇到过求凸包的题目,感觉好难呀,顿时有点难受。毕竟自己计算几何的基本功不太扎实,留下了不学无术的泪水。

真正的解法,其实并没有印象中计算几何的题目那么难。需要用到的知识:叉积+最小环。为什么这么说呢?首先要知道,叉积可以用来验证所有点是否在线段的同一边,如果所有点都在同一边,叉积要么同时非负,要么同时非正。我们可以结合以下多边形图片看看。

2020 年百度之星·程序设计大赛 - 测试赛   度度熊保护村庄   计算几何(叉积)+floyd(最小环)

如上图所示的多边形,如果我们判定点O是否在多边形内 ,我们可以沿着顺时针方向看, 顶点A和B组成的边AB可看作是一条向量,A指向B ,同理顶点A和O组成的边AO可看作是一条向量,A指向O。根据右手法则,向量AO与向量AB的叉积为正。根据右手法则,向量BO与向量BC的叉积也为正。… … 可以证明,如果按顺逆时针方向,多边形上任意点(假设为点X),与点O相连形成的向量XO,以及点X与“点X在顺逆时针方向多边形上的下一个点“(假设为点Y)形成的向量XY,那么XO与XY的叉积永远为正。 这里可参考博客 https://blog.csdn.net/ezhchai/article/details/78841336

根据右手法则,我们可以知道,AD与AB的叉积为负,AO与AB的叉积为正,由于正负性不同,所以我们知道点O与点D分别在AB的不同侧。 这就是判断点与多边形关系的一个直接思路:多边形可看做从某点出发的闭合回路,内部的点永远在回路的同一边。

在了解了叉积判断点是否在线段的同一侧的原理后,我们有一个想法:一切可能构成包住所有房子的回路的边都连起来。我们枚举所有伙伴的坐标连接的线段,利用叉积判断是不是所有的住房都在线段的同一侧,如果是,则可以把这两个伙伴坐标点连起来(连接的边的权值为1,权值为0表示两点直接没有边连接)。

在连接完符合要求的边之后,我们可以用floyd算法求最小环。这里可参考博客 https://oi-wiki.org/graph/min-circle/

经过建边和求最小环的操作之后,若有解,答案就是m-最小环的长度。时间复杂度为O(m^3)。

Code

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=520;
int n,m,ans=-1;
int Connect[N][N];

struct Point
{
    int x,y;
    Point() {}
    Point(int _x,int _y):x(_x),y(_y) {}

    Point operator - (const Point &p)const //重载向量减法
    {
        return Point(x-p.x,y-p.y);
    }
} bear[N],house[N];

int CrossProduct(Point A,Point B) //求向量A,B的叉积,即A x B
{
    return (A.x*B.y)-(B.x*A.y);
}

int main()
{
#ifdef LOCAL
    freopen("in.txt","r",stdin);
#endif
    while(~scanf("%d",&n))
    {
        //初始化操作
        ans=-1;
        memset(Connect,0,sizeof(Connect));

        for(int i=0; i<n; i++) //输入住房坐标
        {
            scanf("%d%d",&house[i].x,&house[i].y);
        }

        scanf("%d",&m);
        for(int i=0; i<m; i++) //输入伙伴的坐标
        {
            scanf("%d%d",&bear[i].x,&bear[i].y);
        }

        for(int i=0; i<m; i++)  //建边操作
        {
            for(int j=0; j<m; j++)
            {
                if(i==j)continue;
                bool CanConnect=true;
                for(int k=0; k<n; k++)
                {
                    if(CrossProduct(house[k]-bear[i],bear[j]-bear[i])<0)//计算叉积能够判断所有house是否全部在bear[i]、bear[j]两点连线的一侧
                    {
                        CanConnect=false;
                        break;
                    }
                }
                if(CanConnect==true) //若所有house是否全部在bear[i]、bear[j]两点连线的一侧,则可以连接bear[i]和bear[j]
                    Connect[i][j]=1;
            }
        }
        
        //完成以上的建边操作之后,就方便求最小环了
        
        for(int k=0; k<m; k++) //floyd算法求最小环
        {
            for(int i=0; i<m; i++)
            {
                if(Connect[i][k]==0)continue;
                for(int j=0; j<m; j++)
                {
                    if(Connect[k][j]==0)continue;
                    if(Connect[i][j]==0||Connect[i][k]+Connect[k][j]<Connect[i][j])
                        Connect[i][j]=Connect[i][k]+Connect[k][j];
                }
            }
        }

        for(int i=0; i<n; i++)
        {
            if(Connect[i][i]==0)continue;
            if(ans==-1||Connect[i][i]<ans)
                ans=Connect[i][i];
        }

        if(ans==-1)puts("ToT");
        else printf("%d\n",m-ans);

    }
}

nnect[i][i]==0)continue;
            if(ans==-1||Connect[i][i]<ans)
                ans=Connect[i][i];
        }

        if(ans==-1)puts("ToT");
        else printf("%d\n",m-ans);

    }
}

本文地址:https://blog.csdn.net/weixin_43800577/article/details/107342817