結果

問題 No.1932 動く点 P / Moving Point P
ユーザー SSRSSSRS
提出日時 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 #
プレゼンテーションモードにする

#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;
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0