fork download 
  1. #include <iostream>
  2. #include <queue>
  3. #include <stack>
  4. #include <vector>
  5. #include <climits>
  6. #include <algorithm>
  7. #include <cmath>
  8. using namespace std;
  9. #define SIZE 200005
  10. #define DIRS 6
  11. int countarr[SIZE][DIRS]; //Save count of movement during ith index in jth direction
  12. int previous[SIZE]; //No of degrees turned before ith index
  13.  
  14. int main() {
  15.   int t, n, q, s, e, ie, is;
  16.   char c;
  17.   double x, y;
  18.   double PI = 2*acos(0);
  19.   double cos60 = cos((60.0 * PI)/180.0);
  20.   double sin60 = sin((60.0 * PI)/180.0);
  21.  
  22.   //Distance moved in xdirection for i*60 degrees
  23.   double diffx[] = {1.0, cos60, -cos60, -1.0, -cos60, cos60}; 
  24.   //Distance moved in ydirection for i*60 degrees
  25.   double diffy[] = {0.0, sin60, sin60, 0.0, -sin60, -sin60};
  26.  
  27.   cin >> t;
  28.   while(t--) {
  29.     cin >> n >> q;
  30.     for (int j = 0; j < DIRS; j++) {
  31.       countarr[0][j] = 0;
  32.     }
  33.     previous[0] = 0;
  34.     for (int i = 1; i <= n; i++) { //Save in 1-nth index, to avoid edge cases
  35.       cin>>c;
  36.       for (int j = 0; j < DIRS; j++) { //Calculate no of moves in each direction till jth entry
  37.         countarr[i][j] = countarr[i-1][j]; 
  38.         if ((previous[i-1] + (c - '0'))%DIRS == j) {
  39.           previous[i] = j;
  40.           countarr[i][j]++;
  41.         }
  42.       }
  43.     }
  44.  
  45.     for (int i = 0; i < q; i++) { //For each query
  46.       cin >> s >> e;
  47.       s--;
  48.       x = 0;
  49.       y = 0;
  50.       for (int j = 0; j < DIRS; j++) { //In each direction
  51.     	//Re-map jth direction and add offsets
  52.         x += diffx[(j + DIRS - previous[s])%DIRS]*(countarr[e][j] - countarr[s][j]); 
  53.         y += diffy[(j + DIRS - previous[s])%DIRS]*(countarr[e][j] - countarr[s][j]);
  54.       }
  55.       printf("%.8f %.8f\n", x, y);
  56.     }
  57.   }
  58.   return 0;
  59. }
  60.  
Success #stdin #stdout 0s 4408KB
comments (?)
stdin 
1
3 3
012
1 1
1 2
2 2
stdout 
1.00000000 0.00000000
1.50000000 0.86602540
0.50000000 0.86602540
https://ideone.com/eCUP9U
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!