SHARE
TWEET

Untitled

a guest Aug 21st, 2019 66 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. #define F first
  3. #define S second
  4. using namespace std;
  5. using ll = long long int;
  6. using ii = pair<int, int>;
  7. using vi = vector<int>;
  8. using vii = vector<ii>;
  9. using graph = vector<vi>;
  10. const int MAXN = 2e3 + 5;
  11. const int INF = 0x3f3f3f3f;
  12. const int mod =998244853;
  13.  
  14. int ord[] = {1, 2, 3};
  15. int x[4], y[4], xt[4], yt[4];
  16. bool work(int t, int a, int b, int at, int bt) {
  17.     return abs(a-at)+ abs(b-bt) <= 2*t;
  18. }
  19.  
  20. int bbin(int a, int b, int at, int bt, int w) {
  21.     int ini = 1, fim = 3e5, mid, ans = INF;
  22.     while (ini <= fim) {
  23.         mid = ini + fim >> 1;
  24.         if (work(mid,a ,b, at+mid*xt[w], bt+mid*yt[w])) {
  25.             ans = mid;
  26.             fim = mid-1;
  27.         } else {
  28.             ini = mid+1;
  29.         }
  30.     }
  31.     return ans;
  32. }
  33.  
  34. int main() {
  35.     int n, m;
  36.     int a, b;
  37.     int ans, t;
  38.     char c;
  39.     while (scanf("%d %d", &n, &m) != EOF && n) {
  40.         for (int i = 1; i<=3; ++i) {
  41.             scanf("%d %d %c", &a, &b, &c);
  42.             yt[i] = c == 'C';
  43.             xt[i] = c == 'D';
  44.             x[i] = a, y[i] = b;
  45.         }
  46.  
  47.         ans = INF;
  48.         do {
  49.             ii last = {n, m};
  50.             t = 0;
  51.             for (int i = 0, w; i<3; ++i) {
  52.                 w = ord[i];
  53.                 t += bbin(last.F, last.S, x[w]+t*xt[w], y[w]+t*yt[w], w);
  54.                 last = {x[w]+t*xt[w], y[w]+t*yt[w]};
  55.             }
  56.             ans = min(ans, t);
  57.         } while (next_permutation(ord, ord+3));
  58.         printf("%d\n", ans);
  59.     }
  60. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top