2020 ICPC Asia East Continent Final F. Rooks（排序）

Prof. Pang plays chess against his rival Prof. Shou. They are the only two players in the game. The chessboard is very large and can be viewed as a 2D plane. Prof. Pang placed ??1n1 rooks and Prof. Shou placed ??2n2 rooks. Each rook is a point with integer coordinates on the chessboard. One rook is attacked by another rook if they satisfy all of the following conditions:

• They are placed by different players.
• They have the same ??x-coordinate or ??y-coordinate.
• There is no other rook on the line segment between them.

Help Prof. Pang and Prof. Shou to decide which rooks are attacked.

Input

The first line contains two integers ??1,??2n1,n2 (1≤??1,??2≤2000001≤n1,n2≤200000) separated by a single space denoting the number of rooks placed by Prof. Pang and the number of rooks placed by Prof. Shou.

The ??i-th (1≤??≤??11≤i≤n1) line of the next ??1n1 lines contains two integers ??,??x,y (?109≤??,??≤109?109≤x,y≤109) separated by a single space denoting the location (??,??)(x,y) of the ??i-th rook placed by Prof. Pang.

The ??i-th (1≤??≤??21≤i≤n2) line of the next ??2n2 lines contains two integers ??,??x,y (?109≤??,??≤109?109≤x,y≤109) separated by a single space denoting the location (??,??)(x,y) of the ??i-th rook placed by Prof. Shou.

It is guaranteed that the ??1+??2n1+n2 rooks placed by the players are distinct (i.e., no two rooks can have the same location).

Output

Output a string with length ??1n1 on the first line. The ??i-th (1≤??≤??11≤i≤n1) character should be 11 if the ??i-th rook placed by Prof. Pang is attacked and 00 otherwise.

Output a string with length ??2n2 on the second line. The ??i-th (1≤??≤??21≤i≤n2) character should be 11 if the ??i-th rook placed by Prof. Shou is attacked and 00 otherwise.

Example

input

Copy

3 2
0 0
0 1
1 0
0 -1
-1 0

output

Copy

100
11

EC final的签到，对所有点分别排两次序，即先x从小到大再y从小到大；先y从小到大再x从小到大。这样就能很快知道一个点的左右最近的以及上下最近的是不是对手的点了。结构体里可以记录这个点的player以及id等，方便直接更改答案字符串。

#include <bits/stdc++.h>
using namespace std;
int n1, n2;
struct point {
	bool player;
	int id;
	int x, y;
};
bool cmp1(point a, point b) {
	if(a.x != b.x) return a.x < b.x;
	else return a.y < b.y;
}
bool cmp2(point a, point b) {
	if(a.y != b.y) return a.y < b.y;
	else return a.x < b.x;
}
vector<point> v1, v2;
char ans1[200005], ans2[200005];
int main() {
	cin >> n1 >> n2;
	for(int i = 1; i <= n1; i++) {
		int x, y;
		cin >> x >> y;
		point tmp;
		tmp.player = 0;
		tmp.id = i;
		tmp.x = x;
		tmp.y = y;
		v1.push_back(tmp);
		v2.push_back(tmp);
	}
	for(int i = 1; i <= n2; i++) {
		int x, y;
		cin >> x >> y;
		point tmp;
		tmp.player = 1;
		tmp.id = i;
		tmp.x = x;
		tmp.y = y;
		v1.push_back(tmp);
		v2.push_back(tmp);
	}
	sort(v1.begin(), v1.end(), cmp1);
	sort(v2.begin(), v2.end(), cmp2);

	for(int i = 0; i < v1.size(); i++) {
		if(i > 0) {
			if(v1[i - 1].player != v1[i].player && (v1[i - 1].x == v1[i].x || v1[i - 1].y == v1[i].y)) {
				if(v1[i].player == 0) ans1[v1[i].id] = ‘1‘;
				else ans2[v1[i].id] = ‘1‘;
			}
		}
		if(i < v1.size() - 1) {
			if(v1[i + 1].player != v1[i].player && (v1[i + 1].x == v1[i].x || v1[i + 1].y == v1[i].y)) {
				if(v1[i].player == 0) ans1[v1[i].id] = ‘1‘;
				else ans2[v1[i].id] = ‘1‘;
			}
		}
	}
	for(int i = 0; i < v2.size(); i++) {
		if(i > 0) {
			if(v2[i - 1].player != v2[i].player && (v2[i - 1].x == v2[i].x || v2[i - 1].y == v2[i].y)) {
				if(v2[i].player == 0) ans1[v2[i].id] = ‘1‘;
				else ans2[v2[i].id] = ‘1‘;
			}
		}
		if(i < v2.size() - 1) {
			if(v2[i + 1].player != v2[i].player && (v2[i + 1].x == v2[i].x || v2[i + 1].y == v2[i].y)) {
				if(v2[i].player == 0) ans1[v2[i].id] = ‘1‘;
				else ans2[v2[i].id] = ‘1‘;
			}
		}
	}
	for(int i = 1; i <= n1; i++) {
		if(ans1[i] == ‘1‘) cout << "1";
		else cout << "0";
	}
	cout << endl;
	for(int i = 1; i <= n2; i++) {
		if(ans2[i] == ‘1‘) cout << "1";
		else cout << "0";
	}
	return 0;
}

2020 ICPC Asia East Continent Final F. Rooks（排序）

原文：https://www.cnblogs.com/lipoicyclic/p/14762562.html