結果

問題 No.1932 動く点 P / Moving Point P
コンテスト
ユーザー SSRS
提出日時 2022-05-06 22:05:33
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 633 ms / 6,000 ms
コード長 2,190 bytes
コンパイル時間 1,492 ms
コンパイル使用メモリ 176,716 KB
実行使用メモリ 27,644 KB
最終ジャッジ日時 2024-07-05 23:19:49
合計ジャッジ時間 19,570 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 11
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;
const double PI = acos(-1);
struct monoid{
  double xx, xy, x1, yx, yy, y1;
  monoid(): xx(1), xy(0), x1(0), yx(0), yy(1), y1(0){
  }
};
monoid f(monoid L, monoid R){
  monoid ans;
  ans.xx = R.xx * L.xx + R.xy * L.yx;
  ans.xy = R.xx * L.xy + R.xy * L.yy;
  ans.x1 = R.x1 + R.xx * L.x1 + R.xy * L.y1;
  ans.yx = R.yx * L.xx + R.yy * L.yx;
  ans.yy = R.yx * L.xy + R.yy * L.yy;
  ans.y1 = R.y1 + R.yx * L.x1 + R.yy * L.y1;
  return ans;
}
template <typename T>
struct segment_tree{
	int N;
	vector<T> ST;
	function<T(T, T)> f;
	T E;
	segment_tree(vector<T> A, function<T(T, T)> f, T E): f(f), E(E){
		int n = A.size();
		N = 1;
		while (N < n){
			N *= 2;
		}
		ST = vector<T>(N * 2 - 1, E);
		for (int i = 0; i < n; i++){
			ST[N - 1 + i] = A[i];
		}
		for (int i = N - 2; i >= 0; i--){
			ST[i] = f(ST[i * 2 + 1], ST[i * 2 + 2]);
		}
	}
	void update(int k, T x){
		k += N - 1;
		ST[k] = x;
		while (k > 0){
			k = (k - 1) / 2;
			ST[k] = f(ST[k * 2 + 1], ST[k * 2 + 2]);
		}
	}
	T query(int L, int R, int i, int l, int r){
		if (R <= l || r <= L){
			return E;
		} else if (L <= l && r <= R){
			return ST[i];
		} else {
			int m = (l + r) / 2;
			return f(query(L, R, i * 2 + 1, l, m), query(L, R, i * 2 + 2, m, r));
		}
	}
	T query(int L, int R){
		return query(L, R, 0, 0, N);
	}
};
int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout << fixed << setprecision(10);
  int N;
  cin >> N;
  vector<double> p(N), q(N), r(N);
  for (int i = 0; i < N; i++){
    cin >> p[i] >> q[i] >> r[i];
  }
  vector<monoid> A(N);
  for (int i = 0; i < N; i++){
    double t = (double) r[i] / 180 * PI;
    A[i].xx = cos(t);
    A[i].xy = -sin(t);
    A[i].x1 = sin(t) * q[i] - cos(t) * p[i] + p[i];
    A[i].yx = sin(t);
    A[i].yy = cos(t);
    A[i].y1 = -sin(t) * p[i] - cos(t) * q[i] + q[i];
  }
  segment_tree<monoid> ST(A, f, monoid());
  int Q;
  cin >> Q;
  for (int i = 0; i < Q; i++){
    int s, t;
    double x, y;
    cin >> s >> t >> x >> y;
    s--;
    monoid res = ST.query(s, t);
    double x2 = res.x1 + res.xx * x + res.xy * y;
    double y2 = res.y1 + res.yx * x + res.yy * y;
    cout << x2 << ' ' << y2 << endl;
  }
}
0