洪水(flood)

题目背景

Awson是某国际学校信竞组的一只菜鸡。今年，该市发生了千年难遇的洪水。被监禁在学校的Awson不甘怠堕，想将自己投入到公益服务事业中去。这天，他偷了H老师的小电驴，偷偷地溜出校。

题目描述

他观察了一下整个城市的概况，发现学校校门所在地的坐标为（X，Y）。城市共有不超过100条街道，知道每条街道的起止点坐标，街道是笔直双向的，每个方向一个车道。并且确保街道是相互连通的。他每第一次走过一侧车道，满目疮夷，生灵涂炭，百感交集：或触景生情，感慨大自然的残酷，悠悠长叹；或豪情壮志，抒发自己满腔热血，气势豪迈。导致他车速只有20km/h。若这条路的这侧他不是第一次走，车速将提高到50km/h。他可以在任意交叉口、或任何街道的末尾任意转向，包括转U型弯，并且不会耗时。他想知道游历所有街道，并且回到学校最短耗时，精确到分钟。

输入输出格式

输入格式：

输入数据多行。

第1行两个整数X，Y

接下来每行四个整数代表街道起止点坐标，单位米，不超过100行，文件末尾以’EOF’结束。

输出格式：

共1行，两个整数，代表时间，中间用’:’（半角字符，不含引号）隔开。

输入输出样例

输入样例#1：

0 0

0 0 10000 10000

5000 -10000 5000 10000

5000 10000 10000 10000

输出样例#1：

3:55

说明

样例解释：

共3小时55分钟走完全城。

数据规模：

所有坐标可能为负，但保证均为整数，且在长整形（C++中的int）范围内。

题解：

我们考虑到图无环，所以所有街道的两侧都是要走的。

这时我们将每条街道拆成两条单侧道，发现所有节点的度均为偶数，这个图就是一个欧拉图，从任意一个节点都可以不重复地走过所有的边。

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<cmath>

#include<algorithm>

#include<queue>

using namespace std;

typedef long long lol;

double x,y,a,b,c,d,ans;

int main()

{

    scanf("%lf%lf",&x,&y);

    while(scanf("%lf%lf%lf%lf",&a,&b,&c,&d)!=EOF)

    {

        a/=;b/=;c/=;d/=;

        ans+=sqrt((d-b)*(d-b)+(c-a)*(c-a));

    }

    ans=ans/;

    cout<<(int)ans<<':';

    ans-=(int)ans;

    int a=(int)(*ans+0.5);

    if(a<)cout<<''<<a;

    else cout<<a;

    return ;

}

我们只需统计所有街道的长度，由于是双向车道，再将长度×2。最后除以20km/h的速度即可。注意单位的换算。

巴特西

洪水(flood)

洪水(flood)

题目背景

题目描述

输入输出格式

输入输出样例

说明

最新文章

热门文章