yukicoder : No.1999 Lattice Teleportation

これはすんなり解けた。
https://yukicoder.me/problems/no/1999

問題

N個の2次元ベクトル(A[i],B[i])が与えられる。
原点にある点に対し、各ベクトルに応じ以下の移動を行う。

• 現在位置を(x,y)とするとき、(x,y)と(x+A[i],y+B[i])の線分上のどこかの座標に移動する。

途中で格子点以外に止まっても良いが、最後は格子点に止まらないといけないとする。
到達可能な格子点は何通りか。

解法

問題文では移動に順序があるように見えるが、順序は無視して考えて差し支えない。

まずA[i]が負のケースを無視することを考える。
A[i]が負の場合、

• (x,y)と(x+A[i],y+B[i])の線分上のどこかの座標に移動する

と

• (x+A[i]-A[i],y+B[i]-B[i])と(x,y)の線分上のどこかの座標に移動する

を比較すると、点全体が(A[i],B[i])だけ平行移動するだけで、ベクトルを(-A[i],-B[i])と置き換えても解に影響ないことがわかる。

次に、これらのベクトルを使って移動可能な領域を多角形の形で求めよう。
これは単純で、ベクトルを偏角の大きい順に最大限移動した場合に点が移動する経路と、ベクトルを偏角の小さい順に最大限移動した場合に点が移動する経路を合わせると、それらの経路の描く多角形の内側が移動可能な領域となる。

あとはピックの定理で多角形内の格子点を数えよう。

int N;
const ll mo=1000000007;
vector<pair<ll,ll>> V;
vector<pair<__int128,__int128>> P;

bool cmp(pair<ll,ll>& L,pair<ll,ll>& R) {
	return L.first*R.second<L.second*R.first;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>x>>y;
		if(x<0) {
			x=-x;
			y=-y;
		}
		if(x||y) V.push_back({x,y});
	}
	
	
	sort(ALL(V),cmp);
	
	ll B=0;
	P.push_back({0,0});
	FOR(i,V.size()) {
		P.push_back(P.back());
		P.back().first+=V[i].first;
		P.back().second+=V[i].second;
		B+=__gcd(abs(V[i].first),abs(V[i].second));
	}
	FOR(i,V.size()) {
		P.push_back(P.back());
		P.back().first-=V[i].first;
		P.back().second-=V[i].second;
		B+=__gcd(abs(V[i].first),abs(V[i].second));
	}
	
	__int128 A=0;
	FOR(i,P.size()-1) {
		A+=P[i+1].first*P[i].second-P[i].first*P[i+1].second;
	}
	if(A<0) A=-A;
	__int128 ret=(A-B+2)/2+B;
	cout<<(ll)(ret%mo)<<endl;
	
}

まとめ

Convex-hullを明に取る必要があるかと思ったけど、よく考えたら無かった。