Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- bool isDiag = false;
- long pref[100001];
- vector<pair<int, int>> listV;
- int N ;
- int ans = INT_MAX;
- int cal(int x1, int y1, int x2, int y2){
- int res = abs(x1 - x2) + abs(y1-y2);
- return res;
- }
- int main(){
- //isDiag = true;
- if (isDiag)
- {
- //marathon_bronze
- freopen( "marathon_bronze/4.in", "r", stdin);
- }else{
- freopen( "marathon.in", "r", stdin);
- }
- cin >> N ;
- int x, y, lx, ly;
- long sum = 0;
- {
- cin >> lx >> ly;
- listV.push_back({lx,ly});
- pref[1] = sum;
- if(isDiag) cout << "i: " << 1 << "(" << lx << ", " << ly << ") " << endl;
- }
- for (int i = 1; i < N; i++)
- {
- cin >> x >> y;
- listV.push_back({x,y});
- int va = cal(x, y, lx, ly);
- sum += va;
- pref[i+1] = sum;
- if(isDiag) cout << "i: " << i + 1 << "(" << x << ", " << y << ") " << ", va: " << va << ", pref: " << pref[i+1] << ", old: " << "(" << lx << ", " << ly << ")" << endl;
- lx = x;
- ly = y;
- }
- for (int i = 2; i < N; i++)
- {
- int fo = 1;
- int to = i - 1;
- int dist = pref[to] - pref[fo];
- int next = to+1;
- int dist2 = pref[N] - pref[next+1];
- pair<int, int> p1 = listV[to-1];
- pair<int, int> p2 = listV[next];
- int dist3 = cal(p2.first, p2.second, p1.first, p1.second);
- int sum = dist + dist3 + dist2 ;
- if(isDiag) cout << "skip : " << i << ", sum: " << sum << ", dist: "<< dist << ", dist2: ("<< N << "-" << next +1<< ")"<< dist2
- << ", ( " << fo << "-" << to <<"), next: (" << next << "-" << N << ")" ;
- if (isDiag) cout << " recal: " <<"(" << p1.first<<", " << p1.second<<")"
- << "-" <<"(" << p2.first << ", " << p2.second << ")" << ", dist3: " << dist3<< endl;
- ans = min(ans, sum);
- }
- if(!isDiag) freopen("marathon.out", "w", stdout);
- cout << ans << endl;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
