# UVA10203 Snow Clearing problem solution

A data test point on the passbook is relatively simple and easy to AC.

The original version of UVA is very troublesome. It took a long time to ac. the method is the first AC in Luogu. Let's release the solutions for you to study together.

This is the connection of Luogu's solution:

# https://www.luogu.com.cn/problemnew/solution/UVA10203

Here's the original explanation I sent to you.

• At present, I am the first AC in Baidu search and Luogu. This problem is very time-consuming, it's all about details. Share ideas and code, and study together.

• Briefly introduce the following ideas: with the guarantee of data, it must form the Euler circuit, the latter Euler circuit. Starting from the starting point, take an Euler road or Euler circuit, and then return in the opposite direction, so as to ensure that they are all on the way to shovel snow.

• The data input is very special. The normal value input cannot be used. There is a blank line after the given data group of the original question, and there is also a blank line between each group of data. If the data is read in with normal values, it will be read in across lines. There is no way to know the position of blank lines. So here we use string to read in. When we read in blank lines, we judge manually. When we read in the end character, the result is NULL. Then manually convert the string to a value. File test data, enter the last line without carriage return.

• Data output is also very special. The original English title clearly requires that each line should be followed by a blank line, which is easy to be ignored.

• In the end, I failed to pass this set of test data. I suggest you all test whether the problem is also here, and the details are easy to be ignored:

```
```
• ```  2

0 0
0 0 10000 10000
5000 -10000 5000 10000
5000 10000 10000 10000

0 0
0 0 0 9950```
• Observe the later set of test data. If the output is 00:60, it is wrong.

It should be: 1:00. This detail has taken my mind.

• Here, submit the code of code AC:

• ```/*
Because U-turns are possible, follow the opposite path of departure,
We can definitely go back to the starting point. There is no need to drive empty.

AC Code
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
#define maxn 500
double ans=0;//ans: snow removal distance
char s[maxn];
int blank;//The position of three spaces in a character array
//Starting with idx, convert characters in s to numbers
bool first=true;//First set of results
long long to_data(int idx){
long long t=0;
int flag=1;
if(s[idx]=='-'){
//negative
flag=-1;
idx++;
}
while(s[idx]>='0' && s[idx]<='9'){
t=t*10+(s[idx]-'0');
idx++;
}
return flag*t;
}
//Count the number of spaces in s
int blank_cnt(){
int i=0,cnt=0;
int blank_i=1;//Coordinate position of space
while(s[i]){
if(s[i]==' '){
cnt++;
blank[blank_i++]=i;
}

i++;
}
return cnt;
}
//Main function
void resolve(){
//Two lanes, distance times 2
ans*=2;
ans/=1000;//Unit becomes kilometer

double time=0;//In hours
time=ans/20;
long long hour=floor(time);
long long minute=((time-hour)*60+0.5);
//Round to 60 minutes, hour plus 1, minute clear
if(minute==60){
minute=0;
hour++;
}
if(first){
//Output of the first group of results
printf("%lld:%02lld\n",hour,minute);
first=false;
}else{
//Output a blank line first
printf("\n%lld:%02lld\n",hour,minute);
}

}
int main(){
//  freopen("1374.in","r",stdin);
//  freopen("1374.out","w",stdout);
int t,cnt;
long long x1,y1,x2,y2;
bool first=true;//First set of data
scanf("%d",&t);
getchar();//Consume extra enter
getchar();//Carriage return for blank lines
while(true){
//In the UVA website, gets has been abandoned and cannot be used. Use fgets instead.
//End of input
if(fgets(s,maxn,stdin)==NULL)
break;

cnt=blank_cnt() ;//Count the number of spaces
//Start coordinate position, indicating the start of a new set of data input. Until the next cnt==1
if(cnt==1){
//Data itself can be unnecessary and not processed
//Start of a set of data
//Data initialization
ans=0;
}else if(cnt==3){
//New data input, separating four positive numbers
x1=to_data(0) ;
y1=to_data(blank+1);
x2=to_data(blank+1);
y2=to_data(blank+1);
//Calculate the distance between the vertices, which is necessary for snow shoveling
ans+=sqrt(pow((x1-x2),2.0)+pow((y1-y2),2.0));
}else{
//Blank line, end of a set of data, process data
resolve();
}

}
//Processing the last set of data output
resolve();
return 0;
}
```

• Welcome to discuss improvement, but don't copy!  Published 1 original article · praised 0 · visited 7

Added by eskimowned on Wed, 04 Mar 2020 09:13:58 +0200