求 Hack
查看原帖
求 Hack
385633
Imken楼主2023/7/2 17:47
#include <iostream>
#include <algorithm>
#define is_covered(x0, y0, x1, y1) (y1 >= 0 && y1 <= y0) \
		&& ((x0 - y0) <= x1 && x1 <= (x0 + y0))          \
		&& (((x1 <= x0) && (x1 - y1) >= (x0 - y0)) ||    \
			((x1 > x0) && (x1 + y1) <= (x0 + y0)))
using namespace std;

struct Pos { int x, y; };

bool operator< (Pos a, Pos b) {	return a.y == b.y ? a.x > b.x : a.y > b.y; }

int n, x, y, cnt = 0;

Pos s[100005];
char cov_flag[100005];

int main()
{
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%d%d", &x, &y);
		s[i] = {x, y};
	}
	sort(s + 1, s + 1 + n);
	for (int i = 1; i <= n; i++) {
		if (cov_flag[i]) continue;
		for (int j = 1; j <= n; j++) {
			if (i == j || cov_flag[j] == 1) continue;
			if (is_covered(s[i].x, s[i].y, s[j].x, s[j].y)) {
				cov_flag[j] = 1;
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		if (!cov_flag[i]) cnt++;
	}
	printf("%d", cnt);
}

感觉按 y, x 双关键字排序不是正解 会被卡 但是不知道怎么卡 求 Hack

2023/7/2 17:47
加载中...