UVa10203 - Snow Clearing(Euler Circuit 歐拉迴路)

題目大意

道路上全部都充滿了積雪，你必須用剷雪車，將積雪清除，鏟雪車不鏟學時時速 50 km，鏟雪時 20 km，給你道路上 x1, x2, y1, y2 座標，其中直線距離就是公路距離，再給你鏟學車位置，請告訴我鏟雪車多久才能將所有積雪清除，且回到起始位置。

題目連結

重點觀念

• Euler Circuit 歐拉迴路

分析

• 我們可以知道，歐拉迴路就是將所有的邊(街道)都繞過一遍，因此這題符合歐拉迴路
• 所以我們只要將所有道路的距離都求出來，並且乘以 2(道路是雙向都要清除)，就是答案
• 注意計算時速差。
• 這題的輸入、輸出非常難寫

參考連結

參考 mirror 的 Problem C: Snow Clearing，收益良多

題目程式碼

#include <iostream>
#include <bits/stdc++.h>
#define LOCAL
#define int long long
using namespace std;
int t, a, b;
char s[1024];
int32_t main()
{
    scanf("%d", &t);
    while(getchar() != '\n');
    while(getchar() != '\n');

    while(t--){
        gets(s);
        double x1, x2, y1, y2;
        double dist = 0;
        while(gets(s) && s[0] != '\0'){
            sscanf(s, "%lf %lf %lf %lf", &x1, &y1, &x2, &y2);
            dist += hypot(x1 - x2, y1 - y2); //計算直線距離
        }
        dist = dist / 1000; //換算成功里
        double hour = dist * 2 / 20; //雙向距離，時速 20km
        int mm = (int)round(hour * 60); //換算成分鐘
        printf("%d:%02d\n", mm/60, mm%60);
        //printf("%d:%02d\n", m/60, m%60);
        if(t) puts("");
    }
    return 0;
}