AIM Tech Round 5 : F. Make Symmetrical

これは頑張っておけばよかったなぁ…。
http://codeforces.com/contest/1028/problem/F

問題

２次元座標に対し、第１象限の格子点座標を伴う以下のクエリが与えられるので、適宜対応せよ。

• 頂点を追加する
• 頂点を削除する
• 座標(x,y)が指定される。追加済み頂点群に対し、(0,0)-(x,y)を結ぶ直線に対し線対称となるようにするには、あといくつ点を足せばよいか答える。

解法

３つ目のクエリでは、その時点の頂点数に対し

• 直線上にある点があれば1引く
• 直線上にないが、互いに対象な位置にある点ペアがあれば2引く

を行った値を答えればよい。

ここで、後者について、互いに対称な位置にある点は、原点からの距離が等しい点がポイント。
よって、元の頂点に対し同じ距離同士の物をグループ化しよう。
頂点は格子点だけなので、同じ距離同士の頂点はあんまり数がない。
よってそれらに対し、事前に対象となる直線を求めておけばよい。

int Q,P;
map<ll,set<pair<ll,ll>>> M;
map<pair<ll,ll>,int> del;

pair<ll,ll> getpoint(ll x1,ll y1,ll x2,ll y2) {
	x1+=x2;
	y1+=y2;
	ll g=__gcd(x1,y1);
	return {x1/g,y1/g};
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>Q;
	FOR(i,Q) {
		cin>>j>>x>>y;
		if(j==1 || j==2) {
			ll t=1LL*x*x+1LL*y*y;
			if(j==1) {
				P++;
				M[t].insert({x,y});
				FORR(p,M[t]) {
					auto a=getpoint(p.first,p.second,x,y);
					del[a]++;
					if(p.first!=x || p.second!=y) del[a]++;
				}
			}
			else {
				P--;
				FORR(p,M[t]) {
					auto a=getpoint(p.first,p.second,x,y);
					del[a]--;
					if(p.first!=x || p.second!=y) del[a]--;
				}
				M[t].erase({x,y});
			}
		}
		else {
			int g=__gcd(x,y);
			x/=g;
			y/=g;
			cout<<P-del[{x,y}]<<endl;
		}
	}
}

まとめ

Dよりこっちに時間をかけておけばよかったかなぁ…。