結果
問題 | No.1932 動く点 P / Moving Point P |
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
#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;}}