Advertisement
Guest User

Untitled

a guest
May 1st, 2018
1,431
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.96 KB | None | 0 0
  1. #include <algorithm>
  2. #include <bitset>
  3. #include <complex>
  4. #include <cassert>
  5. #include <deque>
  6. #include <iostream>
  7. #include <iomanip>
  8. #include <istream>
  9. #include <iterator>
  10. #include <map>
  11. #include <math.h>
  12. #include <memory>
  13. #include <ostream>
  14. #include <queue>
  15. #include <set>
  16. #include <sstream>
  17. #include <stack>
  18. #include <string>
  19. #include <string.h>
  20. #include <time.h>
  21. #include <vector>
  22.  
  23. #define INF_MAX 2147483647
  24. #define INF_MIN -2147483647
  25. #define INF_LL 4000000000000000000LL
  26. #define INF 1000000000
  27. #define EPS 1e-8
  28. #define LL long long
  29. #define mod 1000000007
  30. #define pb push_back
  31. #define mp make_pair
  32. #define f first
  33. #define s second
  34. #define setzero(a) memset(a,0,sizeof(a))
  35. #define setdp(a) memset(a,-1,sizeof(a))
  36. #define bits(a) __builtin_popcountll(a)
  37.  
  38. using namespace std;
  39.  
  40. typedef pair<long double, long double> point;
  41.  
  42. const long double PI = acosl(-1);
  43.  
  44. point arr[200009];
  45. long double dist[200009], ang[200009];
  46.  
  47. point get_centroid(int n) {
  48.   long double area = 0.0, tmp;
  49.   point a, b, res = point(0, 0);
  50.   for (int i = 0; i < n; i++) {
  51.     a = arr[i], b = arr[(i + 1) % n];
  52.     tmp = a.f * b.s - b.f * a.s;
  53.     area += tmp;
  54.     res.f += (a.f + b.f) * tmp;
  55.     res.s += (a.s + b.s) * tmp;
  56.   }
  57.   area *= 0.5;
  58.   res.f /= (area * 6);
  59.   res.s /= (area * 6);
  60.   return res;
  61. }
  62.  
  63. point get(int ind, const point &centroid, const double &angle) {
  64.   point ans;
  65.   ans.f = centroid.f + dist[ind] * cosl(angle + ang[ind]);
  66.   ans.s = centroid.s + dist[ind] * sinl(angle + ang[ind]);
  67.   return ans;
  68. }
  69.  
  70. long double get_dist(const point &a, const point &b) {
  71.   return sqrtl((a.f - b.f) * (a.f - b.f) + (a.s - b.s) * (a.s - b.s));
  72. }
  73.  
  74. int main() {
  75.   int n, q;
  76.   double a, b;
  77.   cin >> n >> q;
  78.   for (int i = 0; i < n; i++) {
  79.     scanf("%lf %lf", &a, &b);
  80.     arr[i] = point(a, b);
  81.   }
  82.   long double zbx=arr[0].first,zby=arr[0].second;
  83.   for(int i=0; i < n; i++)
  84.   {
  85.       arr[i].first-=zbx;
  86.       arr[i].second-=zby;
  87.   }
  88.   int i = 0, j = 1, c, x, y;
  89.   point centroid = get_centroid(n), top, nxt;
  90.   long double angle = 0;
  91.   for (int i = 0; i < n; i++) {
  92.     dist[i] = get_dist(arr[i], centroid);
  93.     ang[i] = atan2l(arr[i].s - centroid.s, arr[i].f - centroid.f);
  94.     if (ang[i] < 0)
  95.       ang[i] += 2 * PI;
  96.   }
  97.   while (q--) {
  98.     scanf("%d", &c);
  99.     if (c == 1) {
  100.       scanf("%d %d", &x, &y);
  101.       x--, y--;
  102.       if (x == i) {
  103.         i = y;
  104.         top = get(j, centroid, angle);
  105.         nxt = point(top.f, top.s - dist[j]);
  106.       } else {
  107.         j = y;
  108.         top = get(i, centroid, angle);
  109.         nxt = point(top.f, top.s - dist[i]);
  110.       }
  111.       angle += -PI / 2 - atan2l(centroid.s - top.s, centroid.f - top.f);
  112.       while (angle < 0)
  113.         angle += 2 * PI;
  114.       while (angle > 2 * PI)
  115.         angle -= 2 * PI;
  116.       centroid = nxt;
  117.     } else {
  118.       scanf("%d", &x);
  119.       top = get(x - 1, centroid, angle);
  120.       printf("%.10lf %.10lf\n", (double) (top.f+zbx), (double) (top.s+zby));
  121.     }
  122.   }
  123.   return 0;
  124. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement