首页 > 其他 > 详细

HDU - 6080 :度度熊保护村庄 (凸包,floyd最小环)(VJ1900题达成)

时间:2019-04-21 20:51:41      阅读:417      评论:0      收藏:0      [点我收藏+]

pro:二维平面上,给定N个村庄。M个士兵驻守,把村庄围住,现在我们想留下更多的士兵休息,使得剩下的士兵任然满足围住村庄。N,M<500;

sol:即是要找一个最小的环,环把村庄围住。 由于是环, 最小的点数等价于最小的边数。 所以我们求最小的边数,而士兵之间能有有向边,当且仅当所有的村庄在有向边的左边(逆时针连边)。 然后就是floyd最小环。

#include<bits/stdc++.h>
#define ll long long
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int maxn=510;
const int inf=1e9;
const double pi=acos(-1.0);
struct point{
    int x,y;
    point(){}
    point(int xx,int yy):x(xx),y(yy){}
}a[maxn],b[maxn];
ll det(point a,point b){ return a.x*b.y-a.y*b.x;}
ll dot(point a,point b){ return a.x*b.x+a.y*b.y;}
point operator +(point a,point b){ return point(a.x+b.x,a.y+b.y);}
point operator -(point a,point b){ return point(a.x-b.x,a.y-b.y);}
int dis[maxn][maxn];
int main()
{
    int N,M,ans;
    while(~scanf("%d",&N)){
        rep(i,1,N) scanf("%d%d",&a[i].x,&a[i].y);
        scanf("%d",&M);
        rep(i,1,M) scanf("%d%d",&b[i].x,&b[i].y);
        rep(i,1,M) rep(j,1,M) dis[i][j]=inf;
        ans=inf;
        rep(i,1,M)
         rep(j,1,M){
             if(i==j) continue;
             bool F=1;
             rep(k,1,N){
                 if(det(b[j]-b[i],a[k]-b[i])<0){
                    F=0; break;
                 }
             }
             if(F) dis[i][j]=1;
        }
        rep(k,1,M)
         rep(i,1,M) if(dis[i][k]!=inf) //删去后很慢
          rep(j,1,M) dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
        rep(i,1,M) ans=min(ans,dis[i][i]);
        if(ans==inf) puts("ToT");
        else printf("%d\n",M-ans);
    }
    return 0;
}

 

HDU - 6080 :度度熊保护村庄 (凸包,floyd最小环)(VJ1900题达成)

原文:https://www.cnblogs.com/hua-dong/p/10746658.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!