Codeforces ECR #108 : E. Off by One

また難易度勾配が極端な回。
https://codeforces.com/contest/1519/problem/E

問題

2次元座標上にN個の点がある。
以下の処理を繰り返し、N個の点を2つずつ対にして取り除くとき、最大何対の頂点を取り除けるか。
取り除き方の一例を求めよ。

• 2つの点a,bを選ぶ。
• それぞれ、X座標かY座標のいずれかを1増加させる。
• 原点とaとbが一直線上に並ぶとき、取り除ける。

解法

以下のグラフを考える。

• 原点からの偏角に対応する点
• 入力のそれぞれに対応する点

後者の点からは、X座標とY座標を1ずらしたときの偏角それぞれに対し2本の辺が出る。
あとはこのグラフで、「入力のそれぞれに対応する点」のうち2点を端点とする長さ2のパスをできるだけ取り除きたい。
これはこのグラフのDFS木を考え、貪欲にマッチングを取っていけばよい。

int N;
ll A,B,C,D;
map<pair<ll,ll>,vector<int>> cand;
set<pair<int,int>> E[404040];
vector<int> V[404040];

vector<pair<int,int>> R;

int dfs(int cur,int pe) {
	int oth=-1;
	while(E[cur].size()) {
		int tar=E[cur].begin()->first;
		int e=E[cur].begin()->second;
		E[cur].erase(E[cur].begin());
		E[tar].erase({cur,e});
		e=dfs(tar,e);
		if(e!=-1) {
			if(oth==-1) {
				oth=e;
			}
			else {
				R.push_back({e+1,oth+1});
				oth=-1;
			}
		}
	}
	if(oth==-1) {
		return pe;
	}
	else if(pe!=-1) {
		R.push_back({pe+1,oth+1});
		return -1;
	}
	else return -1;
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>A>>B>>C>>D;
		ll p=C*B;
		ll q=D*(A+B);
		ll g=__gcd(p,q);
		cand[{p/g,q/g}].push_back(i);
		p=(C+D)*B;
		q=D*A;
		g=__gcd(p,q);
		cand[{p/g,q/g}].push_back(i);
	}
	
	x=0;
	FORR2(c,v,cand) {
		FORR(e,v) V[e].push_back(x);
		x++;
	}
	FOR(i,N) {
		E[V[i][0]].insert({V[i][1],i});
		E[V[i][1]].insert({V[i][0],i});
	}
	
	FOR(i,404040) dfs(i,-1);
	cout<<R.size()<<endl;
	FORR2(a,b,R) cout<<a<<" "<<b<<endl;
	
}

まとめ

本番はマッチング問題を無理に最大フローに落としこもうとして失敗した。