Codeforces Round#24 C:Sequence of points

keyword

幾何　C++

概要

点M_0とA_0,A_1,…,A_(n-1)が与えられる。このとき点列M_iをA_(i-1 mod n)に関してM_i-1と対象な点として定めるときM_jの座標を求める問題(n<10^5,nは奇数, j<10^18)。
jが大きいので、きっとMは周期を持つか回転をするんだろうなと予測。とりあえずサンプルで点列の座標を出力してみると2*nで元の位置に戻ってる。他のケースも試してみようとおもってn=2のサンプルを作ると発散気味。予想は間違いだと踏んで真面目に考えてみる。これって線形写像だっけとか色々考えている内にnが奇数であることに気づく。n=7で実験すると正しそう。これだ。修正して送信するとRE。はいはいいつものsegmentation faultね、とか思いながら確認するもそれは大丈夫そう。なぜ？と思って色々修正するけどやっぱりRE。ダメ元でscanfをcinに変えたらAC。後で確認したところlong longは%lldではなくて%I64dとする必要があったらしい。

typedef pair<ll, ll> pi;

pi mirror(pi a, pi b){
    return MP(2*a.fs-b.fs, 2*a.sc-b.sc);
}

int main(){
    ll i;
    ll n, JJ, jj;
    cin >> n >> JJ;
    jj = JJ%(2*n);
    ll x, y;
    vector<pi> ps(n);
    cin >> x >> y;
    pi m = MP(x,y);
    REP(i,n){
        cin >> x >> y;
        ps[i] = MP(x,y);
    }
    REPONE(i,jj){
        m = mirror(ps[(i+n-1)%n], m);
    }
    cout << m.fs << " " << m.sc << endl;
    return 0;
}