Description
Awson是某国际学校信竞组的一只菜鸡。今年,该市发生了千年难遇的洪水。被监禁在学校的Awson不甘怠堕,想将自己投入到公益服务事业中去。这天,他偷了H老师的小电驴,偷偷地溜出校。
他观察了一下整个城市的概况,发现学校校门所在地的坐标为(X,Y)。城市共有不超过100条街道,知道每条街道的起止点坐标,街道是笔直双向的,每个方向一个车道。并且确保街道是相互连通的。他每第一次走过一侧车道,满目疮夷,生灵涂炭,百感交集:或触景生情,感慨大自然的残酷,悠悠长叹;或豪情壮志,抒发自己满腔热血,气势豪迈。导致他车速只有20km/h。若这条路的这侧他不是第一次走,车速将提高到50km/h。他可以在任意交叉口、或任何街道的末尾任意转向,包括转U型弯,并且不会耗时。他想知道游历所有街道,并且回到学校最短耗时,精确到分钟。
Input
输入数据多行。
第1行两个整数X,Y
接下来每行四个整数代表街道起止点坐标,单位米,不超过100行,文件末尾以’EOF’结束。
Output
共1行,两个整数,代表时间,中间用’:’(半角字符,不含引号)隔开。
Sample Input
0 0
0 0 10000 10000
5000 -10000 5000 10000
5000 10000 10000 10000
Sample Output
3:55
Hint
样例解释:
共3小时55分钟走完全程。
数据规模:
所有坐标可能为负,但保证均为整数,且在长整形(C++中的int)范围内。图无环。
题解
我们考虑到图无环,所以所有街道的两侧都是要走的。
这时我们将每条街道拆成两条单侧道,发现所有节点的度均为偶数,这个图就是一个欧拉图,从任意一个节点都可以不重复地走过所有的边。
我们只需统计所有街道的长度,由于是双向车道,再将长度$×2$。最后除以$20km/h$的速度即可。注意单位的换算。
#include <cmath> #include <cstdio> #include <cstdlib> #include <iomanip> #include <iostream> using namespace std; long double solve(int,int,int,int); int mround(long double); int startx,starty,endx,endy; unsigned int h,m; ; int main() { cin>>startx>>starty; while (cin>>startx>>starty>>endx>>endy) tot += solve(startx,starty,endx,endy); h = floor(tot) - ; m = mround( * (tot - h)); ) { m -= ; h++; } cout<<h<<":"; ) cout<<"; cout<<m<<endl; ; } long double solve(int a,int b,int c,int d) { long double x,y; x = abs(a - c); y = abs(b - d); ; } int mround(long double inp) { if (inp - floor(inp) >= 0.5) ; else return floor(inp); }