結果
| 問題 | No.1932 動く点 P / Moving Point P |
| コンテスト | |
| ユーザー |
 Raymoo_
|
| 提出日時 | 2026-08-21 14:19:04 |
| 言語 | C++23(gcc16) (gcc 16.1.0 + boost 1.90.0) |
| 結果 |
AC
|
| 実行時間 | 500 ms / 6,000 ms |
| + 647µs | |
| コード長 | 9,454 bytes |
| 記録 | |
| コンパイル時間 | 2,201 ms |
| コンパイル使用メモリ | 358,124 KB |
| 実行使用メモリ | 300,040 KB |
| 最終ジャッジ日時 | 2026-08-21 14:19:23 |
| 合計ジャッジ時間 | 17,548 ms |
|
ジャッジサーバーID （参考情報） |
judge3_0 / judge1_0 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 11 |
ソースコード
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pii pair<int, int>
#define bend(v) v.begin(),v.end()
#define vect vector
#define prq priority_queue
#define umap unordered_map
#define eb emplace_back
#define pb push_back
#define pob pop_back
#define ef emplace_front
#define pf push_front
#define pof pop_front
#define el "\n"
#define deb cout<<"\nok\n";return
#define nextl cout<<"\n"
#define lwb lower_bound
#define upb upper_bound
#define rs resize
#define popcnt __builtin_popcountll
#define clz __builtin_clzll
#define ctz __builtin_ctzll
#define ull unsigned long long
#define ll long long
#define dbl long double
#define FILE "ijustwannabepartofyourskibidi"
void IO(){
if(fopen(FILE".in", "r")){
freopen(FILE".in", "r", stdin);
freopen(FILE".out", "w", stdout);
}
else if(fopen(FILE".inp", "r")){
freopen(FILE".inp", "r", stdin);
freopen(FILE".out", "w", stdout);
}
}
const ll N = 1e5 + 10, MOD = 1e9+7, INF = 1000000000000000069;
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
ll rand(ll l, ll r){
return uniform_int_distribution<ll>(l, r)(rng);
}
ll pm(ll a,const int b=MOD){return (a%=b) < 0 ? a + b : a;}
ll sq(ll x){return x*x;}
ll __lcm(ll a, ll b, const ll lim=LLONG_MAX){
if(a == -1 || b == -1)return -1;
ll g = __gcd(a,b);
if(b/g > lim/a)return -1;
return (a/g)*b;
}
const dbl PI = acosl(-1);
struct Matrix{
dbl mat[3][3];
Matrix(){
memset(mat, 0, sizeof mat);
}
auto &operator [](int id){return mat[id];}
const auto &operator [](int id)const{return mat[id];}
void make_identity(){
memset(mat, 0, sizeof mat);
mat[0][0] = mat[1][1] = mat[2][2] = 1;
}
Matrix operator * (const Matrix &o) const{
Matrix res;
for(int i=0; 3>i; i++){
for(int j=0; 3>j; j++){
for(int k=0; 3>k; k++){
res[i][k] += (mat[i][j] * o[j][k]);
}
}
}
return res;
}
};
struct Vector{
dbl vec[3];
Vector(){memset(vec, 0, sizeof vec);}
auto &operator [](int id){return vec[id];}
const auto &operator [](int id)const{return vec[id];};
Vector operator * (const Matrix &o) const{
Vector res;
for(int j=0; 3>j; j++){
for(int k=0; 3>k; k++){
res[k] += vec[j] * o[j][k];
}
}
return res;
}
};
int n, q, masks[N];
Matrix a[N], sus[N][20];
void dnc(int l, int r, int dep){
if(l == r) return;
int mid = (l + r) / 2;
sus[mid][dep] = a[mid];
sus[mid+1][dep] = a[mid+1];
for(int i=mid-1; i>=l; i--) sus[i][dep] = a[i] * sus[i+1][dep];
for(int i=mid+2; r>=i; i++) sus[i][dep] = sus[i-1][dep] * a[i];
for(int i=mid+1; r>=i; i++) masks[i] ^= 1<<dep;
dnc(l, mid, dep+1);
dnc(mid+1, r, dep+1);
}
void sol(){
cin >> n;
for(int i=0; n>i; i++){
dbl p, q, theta;
cin >> p >> q >> theta;
theta = theta / 180.0l * PI;
// cout << theta << ' ' << cosl(PI) << el;
auto &mat = a[i];
mat[0][0] = cosl(theta);
mat[1][0] = -sinl(theta);
mat[2][0] = -p*cosl(theta) + q*sinl(theta) + p;
mat[0][1] = sinl(theta);
mat[1][1] = cosl(theta);
mat[2][1] = -q*cosl(theta) - p*sinl(theta) + q;
mat[0][2] = mat[1][2] = 0;
mat[2][2] = 1;
// for(int i=0; 3>i; i++) for(int j=0; 3>j; j++){
// cout << mat[i][j] << " \n"[j==2];
// }
// nextl;
}
// return;
dnc(0, n-1, 0);
cout << fixed << setprecision(6);
cin >> q;
while(q--){
int l, r;
cin >> l >> r;
l--, r--;
dbl x, y;
cin >> x >> y;
Vector v;
v[0] = x, v[1] = y, v[2] = 1;
if(l == r) v = v * a[l];
else {
int dep = __builtin_ctzll(masks[l] ^ masks[r]);
v = (v * sus[l][dep]) * sus[r][dep];
}
cout << v[0] << ' ' << v[1] << el;
}
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(NULL);cout.tie(NULL);
IO();
int t = 1;
// cin >> t;
while(t--) sol();
}
/*
...-%%%%%%%%%%%...
.:**#%=%%%%%+........-%%%%. .
.%%%%%%=-..%#. .#%%.
%%%+.. .: *%%.
.%%. :. :%%%%%:.
.%%. ... .: :: .=%%%.
..%%. #%#:%. : :.. =%%.
%%+..: .%*::::%-::::::-::::::.. .:-%%%%. .*%%..
.%# :.%:::::::%%%%%%%%%%%%%+...%%%+::::%#. .%%.
.%%. ..:.%=::::*%#***#%::::::::%%%%=:::::::%%. .%%.
=%%%...-%%%:::*%********%:::%%%****%::::::::%% .%-
.%::::%%***%=:%%**********%%********%:::::::=%-:. .%..
#%:::%#*****%%**********************%:::+%%%*%%-.: .::..%%.
.%%::%%*****==**==*****#************#%%%%#******%%..::::.. .%%.
.%%#%+%%***************##*+=+*==********************%%.:. .%%
.%%***%%****************#**==**==******==**+=+********%%%%%%%%% %%.
.#%#*********************%%**************++************%%::::::%* .%%%.
.%%***************#*****%%%****************************%%::::::%% .-%%%.
.#%***************#****%%--%*********%*****************%#::::-%%%%%%%%%%.
.%%**************#**%%%----%********%%**************#***#%%%#**%#******%*
.%%**************#%%%--.....%%*******%%**************#**********#%******%%.
.%%*************%%...........%%******%-%*************#***********%%*****%%.
.%%*************%%...%%%%%.....%%%%%%%.=%%%%%%%%##****#****##::::+%%*****%#
.%%************%%...%. %%.................%%%%-.....%*****#*****%%*****%%
.#%#*#****#****%%:::%- %%.................%. #-....%*****#*#####%#****%%.
.%%##****%%%**%%:::::##...................%= .%+:::%#*****#:####*%%****%%.
.+%%#**%%.#%%%%::::::........###+.:*##-....%%%:::::%*****##******%%****%%-
..%%*%%.......:::.......##..#*...#+..#*....:::::%******#*****##%%*****%%.
.%%%%%................#-##=--##+-+###-#....:::%******#:###*::%%#*****%%.
.%%****%%..............#----------------=*...#%#****##**##::#**%%*******%%.
.%%%%%*=+%%*...........#-----------------#.....#%%%%%%+:##*##:*%%*******%%%.
..:*%====%%%%........#-----------------#:.........%#********%%*****%%%%%%.
.%%=======*%%%%%%%.%%+----#-%------%%#.......%%%%::::::::%%==***#%###%%.
..%%=============+%%-:#%%%%-::%%%%%%::%%%%%%%%%=%%*******%%=====**%%###%%..
-%%%%%%%%%%%%%%%%+%.%+:+%::%::::%::%:::%%#%... .%%******%%%========#%####%%.
.%%++#############%%# ..%%.**%%#%%%%%%%#%***%. :%%*****%%%=+%%%%%%%%%%#####%%.
.%%++++*############*++% .%************#****%. #%*%%%%+++%%%%###############%%.
.+%%%%%%%%%%####+##########*+++++%%. .%**#**********#****% %%**%%%++++###################%:
=%%%%######################++++++++%%*%.-%%#***********#****% .%****%%+++++###################%%
.%%%#######################*%%%%%%%%.%%*#%+%###################%.%%***%%%+++++###################%%
*%%######################+#%%++++++%*. =%*%. .:%%%%########%%%%%%%%%#*#%.%%++#####################%%
.%%%#####################%%%%%+++++++%- %*#%%. .%%%*++++++*%%%....%%#####################%%*
%%######%%%%%#%%%%%######%%.%*+++++++%. %****#. .%%+++*+++++*++%%...=%%###################%%%.
%%%%%%%%#-=##%...%%######%%.%%+++++++%%..*%***#%%%%%. ..%+++++++++++++++%%...%%##################%%%.
.%:. .#%#####%%.%%+++++++++%. %*********%%%%%++++++++++++++++%%...%%##############%%%%..
:%#####%% .%%+++++++%% .%%**********%%++++++++++++++++%%.....%#########%%%%%% .
*%#####%%. .%%+++++++%%:. .%%********%%++++++++++++++++%%....%%%%%%%%%%%%*..
.%%##%%% .%%*+++++++%%. ..#%%%#****%%+++++++++++++++%%%%%% . .....
%%#%%%. .:%%%%%%%%%%%...-%. ......%%+++++++++++++%%.
..%%%. ... .%%%#%%%=:#%%%%%%%%*++++++%%%#
.-%%+. ... .%%%%%%%:.
*/