Advertisement
Doktorkrab

Untitled

Mar 29th, 2017
79
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.95 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define pb push_back
  3. #define err(x) cerr << #x << " is " << x << '\n';
  4.  
  5.  
  6. using namespace std;
  7. typedef double ld;
  8. struct Vector{
  9.     ld x, y;
  10.     Vector(ld x_arg = 0, ld y_arg = 0):x(x_arg), y(y_arg) {}
  11.     friend ostream& operator<<(ostream& os, const Vector& v){
  12.     os << v.x << ' ' << v.y;
  13.     return os;
  14.     }
  15. };
  16. const int MAXN = 1e5;
  17. vector <Vector> fence;
  18. int holes[MAXN / 2], n;
  19. ld hl[MAXN / 2];
  20. ld len(Vector a, Vector b){return sqrt((a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y));}
  21.  
  22. int main(){
  23.     cout.precision(20);
  24.     int l, k;
  25.     cin >> n >> l >> k;
  26.     for (int i = 0; i < k; i++){
  27.         cin >> holes[i];
  28.         holes[i]--;
  29.     }
  30.     for (int i = 0; i < n; i++){
  31.         int x, y;
  32.         cin >> x >> y;
  33.         fence.pb(Vector(x, y));
  34.     }
  35.     int pos = 0;
  36.     ld l1 = 0, fz = 0;
  37.     for (int i = 0; i < n;i++){
  38.         if (i == holes[pos] && !pos){
  39.             fz = l1;
  40.             pos = (pos + 1) % k;
  41.             l1 = 0;
  42.         }
  43.         else if (i == holes[pos]){
  44.             hl[pos] = l1;
  45.             pos = (pos + 1) % k;
  46.             l1 = 0;
  47.         }
  48.         else{
  49.             l1 += len(fence[i], fence[(i + 1) % n]);
  50.         }
  51.     }
  52.     hl[0] = l1 + fz;
  53.     ld s = 0, ans = 0;
  54.     for (int hole_ind = 0;hole_ind < k;hole_ind++){
  55.         s += len(fence[holes[hole_ind]], fence[(holes[hole_ind] + 1) % n]);
  56.         int ind = hole_ind;
  57.         ld nowl = l, ansn = 0;
  58.         bool flag = false;
  59.         while(nowl > 0 && !(flag && ind == hole_ind)){
  60.             ld tmp = len(fence[holes[ind]], fence[(holes[ind] + 1) % n]);
  61.             if (tmp > nowl){
  62.                 ansn += nowl;
  63.                 nowl = 0;
  64.             }
  65.             else{
  66.                 ansn += tmp;
  67.                 nowl -= tmp;
  68.             }
  69.             ind = (ind + 1) % k;
  70.             nowl -= hl[ind];
  71.             flag = true;
  72.         }
  73.         ans = max(ans, ansn);
  74.     }
  75.     cout << s - ans;
  76. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement