2017百度の星-1001-度度の熊は村を保護します(floydは最も小さい環を求めます)

4182 ワード
ショート
度度度熊が村を守る
Accepts: 30
Submissions: 765
Time Limit: 2000/1000 MS (Java/Others)
Memory Limit: 32768/32768 K (Java/Others)
Problem Description
ガチャガチャ村がニャハハ村を襲った!
度度度熊はニャーハハ村を救うために、自分の仲間を連れてニャーハハ村を救助しに行きました!度度度熊と仲間たちはすぐにニャーハハ村の各軍事要地を占拠し、ニャーハハ村をしっかりと守った.
しかし度度度熊は発見し、これは長引く戦いであるため、度度度熊は逸待労で、できるだけ多くの体力を保存し、ザラザラ村の戦士と戦うことにした.
そこで度度度熊はできるだけ多くの人を休ませることにしたが、同時にニャーハハ村の保護を怠ることはできなかった.
言い換えれば、度度度熊はできるだけ多くの人が休むことを望んでおり、残りの人で構成され、ニャーハ村のすべての住宅(境界を含む)を適切に包囲することができる包囲圏が存在している.
すみません、最大何人まで休めますか?
Input
この問題には、いくつかのテストデータが含まれています.
最初の行の整数nは、ニャーハハ村の住宅数を表しています.
次のn行は、行ごとに2つの整数(x 1[i],y 1[i])で、ニャーハハ村の住宅座標を表す.
n+1行目は整数mで、度度熊の兵士数を表す.
次にm行、行ごとに2つの整数(x 2[i],y 2[i])があり、度熊パートナーの座標を表す.
満足:
1<=n,m<=500
-10000<=x1[i],x2[i],y1[i],y2[i]<=10000
Output
最も多い人員の休憩数を出力してください.
村全体を守れないなら「ToT」
Sample Input
Copy 
2
1 1
2 2
4
0 0
0 4
4 2
4 0
1
1 1
2
0 0
0 1

Sample Output
Copy 
1
ToT

Statistic | Submit | Clarifications | Back
および作成:http://blog.csdn.net/haut_ykc/article/details/75571044そっくりです.
凸包の思想によって1発の最も小さい环を求めて、详しくは上のリンクを见て...
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
using namespace std;  
typedef long long  ll;  
#define inf 100000000  
#define  maxn  505  
#define  eps 1e-10  
int d[maxn][maxn],n,m;  
struct node  
{  
    int x,y;  
}a[maxn],b[maxn];  
bool tepan()//           
{  
    int i;  
    for(i=1;i<=n;i++)  
        if(abs(a[i].x-a[1].x)>0 || abs(a[i].y-a[1].y)>0)  
            return 0;  
    for(i=1;i<=m;i++)  
        if(abs(b[i].x-a[1].x)>0 || abs(b[i].y-a[1].y)>0)  
            return 0;  
    printf("%d
",m-1);  
    return 1;  
}  
int work(node a,node b, node c)  
{  
    return (a.x-c.x)*(b.y-c.y)-(a.y-c.y)*(b.x-c.x);  
}  
bool judge(node x,node y)//                    
{  
    if(x.x>y.x)  
        swap(x,y);  
    for(int i=1;i<=n;i++)  
        if(a[i].xy.x)  
            return 0;  
    if(x.y>y.y)  
        swap(x,y);  
    for(int i=1;i<=n;i++)  
        if(a[i].yy.y)  
            return 0;  
    printf("%d
",m-2);  
    return 1;  
}  
int check(node x,node y)  
{  
    int i,t1=0,t2=0;  
    for(i=1;i<=n;i++)  
    {  
        int tmp=work(x,y,a[i]);  
        if(tmp>0)//        
            t1++;  
        if(tmp<0)//        
            t2++;  
        if(t1 && t2)//                
            return 0;  
    }  
    if(t1)  
        return 1;  
    if(t2)  
        return 2;  
    if(judge(x,y))  
        return -1;  
    return 3;  
}  
void floyd()  
{  
    int i,j,k,ans=inf;  
    for(k=1;k<=m;k++)  
        for(i=1;i<=m;i++)  
		{
			if(d[i][k]==inf)
				continue;
            for(j=1;j<=m;j++)  
                d[i][j]=min(d[i][j],d[i][k]+d[k][j]);  
		}
    for(i=1;i<=m;i++)  
        ans=min(ans,d[i][i]);  
    if(ans>=inf || ans<=2)  
        printf("ToT
");  
    else  
        printf("%d
",m-ans);  
}  
void solve()  
{  
    int i,j;  
    for(i=1;i<=m;i++)  
        for(j=i+1;j<=m;j++)  
        {  
            int mark=check(b[i],b[j]);  
            if(mark==-1)  
                return;  
            if(mark==1)  
                d[i][j]=1;  
            if(mark==2)  
                d[j][i]=1;  
            if(mark==3)  
                d[i][j]=d[j][i]=1;  
        }  
    floyd();  
}  
int main(void)  
{  
    int i,j;  
	while(scanf("%d",&n)!=EOF)
	{  
		for(i=1;i<=n;i++)  
			scanf("%d%d",&a[i].x,&a[i].y);//xx     
		scanf("%d",&m);  
		for(i=1;i<=m;i++)  
			scanf("%d%d",&b[i].x,&b[i].y);  
		for(i=1;i<=m;i++)  
			for(j=1;j<=m;j++)  
				d[i][j]=inf;
		if(tepan())  
			return 0;  
		solve();  
	}
    return 0;  
}
MACアドレスの変更方法
NTPに頼らず、Symbol from NEMブロックチェーンで同期された現在時刻を取得する