萌新求助#5 WA掉
查看原帖
萌新求助#5 WA掉
448887
cancan123456楼主2022/3/18 14:24
#include <cstdio>
#include <map>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
const int N = 100005;
int max(int a, int b) {
	return a > b ? a : b;
}
// 水平的线段 
struct Segment0 {
	int l, r, y;
};
// 为了合并线段 
bool operator < (const Segment0 & a, const Segment0 & b) {
	return a.l < b.l;
}
// 输入一个线段并返回 
Segment0 Get0() {
	Segment0 s;
	scanf("%d %d %d", &s.l, &s.r, &s.y);
	return s;
}
// 所有输入的线段 
vector < Segment0 > input0;
// 为了合并线段 
// 线段纵坐标 --> 所有线段 
map < int, set < Segment0 > > merge0;
// 合并完应该有 7 条横向线段 
Segment0 res0[7];
// 有几条 
int cnt0;
// 与上面的差不多 
struct Segment1 {
	int d, u, x;
};
bool operator < (const Segment1 & a, const Segment1 & b) {
	return a.d < b.d;
}
Segment1 Get1() {
	Segment1 s;
	scanf("%d %d %d", &s.d, &s.u, &s.x);
	return s;
}
vector < Segment1 > input1;
map < int, set < Segment1 > > merge1;
Segment1 res1[8];
int cnt1;
// 找连通块 
// 应该有且仅有 5 个连通块 
// 分别是 T H U P C
// 每个集合的线段 
// 只有 fa[i] = i 的 own_segment[i] 有元素 
vector < int > own_segment[15];
int fa[15];
int find(int x) {
	return x == fa[x] ? x : fa[x] = find(fa[x]);
}
void merge(int x, int y) {
	int fx = find(x);
	int fy = find(y);
	if (fx != fy) {
		fa[fy] = fx;
		// 把 fy 的所有元素扔进 fx 里 
		own_segment[fx].insert(own_segment[fx].end(), own_segment[fy].begin(), own_segment[fy].end());
	}
}
// sizecnt[i] 表示大小为 i 的连通块有多少个 
int sizecnt[16];
// seg 号线段是不是水平线段 
bool horizontal(int seg) {
	return 0 <= seg && seg < 7;
}
// seg 号线段是不是竖直线段 
bool vertical(int seg) {
	return 7 <= seg && seg < 15;
}
// 每个水平线段的 l, r, y
// 如果是竖直线段, 则都是 0
int l[15], r[15], y[15];
// 每个竖直线段的 d, u, x
// 如果是水平线段, 则都是 0
int d[15], u[15], x[15];
// 判断 segments 里的线段是不是可以组成一个 T
// 下面的 H, U, P, C 函数同理 
bool T(vector < int > & segments) {
	if (segments.size() == 2) {
		// 枚举所有排列 
		sort(segments.begin(), segments.end());
		do {
			int seg1 = segments[0];
			int seg2 = segments[1];
			if (horizontal(seg1) && vertical(seg2)) {
				bool flag1 = d[seg2] < y[seg1] && y[seg1] == u[seg2];
				bool flag2 = l[seg1] < x[seg2] && x[seg2] < r[seg1];
				if (flag1 && flag2) {
					return true;
				}
			}
		} while (next_permutation(segments.begin(), segments.end()));
	}
	return false;
}
bool H(vector < int > & segments) {
	if (segments.size() == 3) {
		sort(segments.begin(), segments.end());
		do {
			int seg3 = segments[0];
			int seg4 = segments[1];
			int seg5 = segments[2];
			if (vertical(seg3) && horizontal(seg4) && vertical(seg5)) {
				bool flag1 = d[seg3] == d[seg5] && d[seg5] < y[seg4] && y[seg4] < u[seg3] && u[seg3] == u[seg5];
				bool flag2 = x[seg3] == l[seg4] && l[seg4] < r[seg4] && r[seg4] == x[seg5];
				if (flag1 && flag2) {
					return true;
				}
			}
		} while (next_permutation(segments.begin(), segments.end()));
	}
	return false;
}
bool U(vector < int > & segments) {
	if (segments.size() == 3) {
		sort(segments.begin(), segments.end());
		do {
			int seg6 = segments[0];
			int seg7 = segments[1];
			int seg8 = segments[2];
			if (vertical(seg6) && horizontal(seg7) && vertical(seg8)) {
				bool flag1 = d[seg6] == d[seg8] && d[seg8] == y[seg7] && y[seg7] < u[seg6] && u[seg6] == u[seg8];
				bool flag2 = x[seg6] == l[seg7] && l[seg7] < r[seg7] && r[seg7] == x[seg8];
				if (flag1 && flag2) {
					return true;
				}
			}
		} while (next_permutation(segments.begin(), segments.end()));
	}
	return false;
}
bool P(vector < int > & segments) {
	if (segments.size() == 4) {
		sort(segments.begin(), segments.end());
		do {
			int seg9 = segments[0];
			int seg10 = segments[1];
			int seg11 = segments[2];
			int seg12 = segments[3];
			if (vertical(seg9) && horizontal(seg10) && horizontal(seg11) && vertical(seg12)) {
				bool flag1 = d[seg9] < y[seg11] && y[seg11] == d[seg12] && d[seg12] < u[seg9] && u[seg9] == y[seg10] && y[seg10] == u[seg12];
				bool flag2 = x[seg9] == l[seg10] && l[seg10] == l[seg11] && l[seg11] < r[seg10] && r[seg10] == r[seg11] && r[seg11] == x[seg12];
				if (flag1 && flag2) {
					return true;
				}
			}
		} while (next_permutation(segments.begin(), segments.end()));
	}
	return false;
}
bool C(vector < int > & segments) {
	if (segments.size() == 3) {
		sort(segments.begin(), segments.end());
		do {
			int seg13 = segments[0];
			int seg14 = segments[1];
			int seg15 = segments[2];
			if (vertical(seg13) && horizontal(seg14) && horizontal(seg15)) {
				bool flag1 = d[seg13] == y[seg15] && y[seg15] < u[seg13] && u[seg13] == y[seg14];
				bool flag2 = x[seg13] == l[seg14] && l[seg14] == l[seg15] && l[seg15] < r[seg14] && r[seg14] == r[seg15];
				if (flag1 && flag2) {
					return true;
				}
			}
		} while (next_permutation(segments.begin(), segments.end()));
	}
	return false;
}
// own_segment[HUC[0, 1, 2]] 里面存储着可能形成 H, U, C 的线段 
int HUC[3];
int main() {
	// 输入 
	int n;
	scanf("%d", &n);
	for (int op, i = 1; i <= n; i++) {
		scanf("%d", &op);
		if (op == 0) {
			Segment0 s = Get0();
			merge0[s.y].insert(s);
		} else {
			Segment1 s = Get1();
			merge1[s.x].insert(s);
		}
	}
	// 合并水平线段 
	// 注意判断需要有 7 条线段 
	cnt0 = 0;
	for (auto segments : merge0) {
		// 当前的线段 
		Segment0 s;
		s = *(segments.second.begin());
		for (auto seg : segments.second) {
			if (s.r < seg.l) {
				// 出现了一个新的线段 
				if (cnt0 == 7) {
					printf("No");
					return 0;
				}
				res0[cnt0] = s;
				cnt0++;
				s = seg;
			} else {
				s.r = max(s.r, seg.r);
			}
		}
		if (cnt0 == 7) {
			printf("No");
			return 0;
		}
		res0[cnt0] = s;
		cnt0++;
	}
	if (cnt0 != 7) {
		printf("No");
		return 0;
	}
	// 同理 
	cnt1 = 0;
	for (auto segments : merge1) {
		Segment1 s;
		s = *(segments.second.begin());
		for (auto seg : segments.second) {
			if (s.u < seg.d) {
				if (cnt1 == 8) {
					printf("No");
					return 0;
				}
				res1[cnt1] = s;
				cnt1++;
				s = seg;
			} else {
				s.u = max(s.u, seg.u);
			}
		}
		if (cnt1 == 8) {
			printf("No");
			return 0;
		}
		res1[cnt1] = s;
		cnt1++;
	}
	if (cnt1 != 8) {
		printf("No");
		return 0;
	}
	// 初始化并查集 
	for (int i = 0; i < cnt0 + cnt1; i++) {
		fa[i] = i;
	}
	for (int i = 0; i < cnt0 + cnt1; i++) {
		own_segment[i].push_back(i);
	}
	for (int i = 0; i < cnt0; i++) {
		for (int j = 0; j < cnt1; j++) {
			// 枚举两条线段 
			Segment0 & s1 = res0[i];
			Segment1 & s2 = res1[j];
			// 如果相交 
			if (s1.l <= s2.x && s2.x <= s1.r && s2.d <= s1.y && s1.y <= s2.u) {
				// 那么就合并 
				merge(i, j + cnt0);
			}
		}
	}
	// 有几个连通块 
	int cnt = 0;
	for (int i = 0; i < cnt0 + cnt1; i++) {
		if (fa[i] == i) {
			cnt++;
		}
	}
	// 一定有 5 个连通块 
	if (cnt != 5) {
		printf("No");
		return 0;
	}
	for (int i = 0; i < cnt0 + cnt1; i++) {
		if (fa[i] == i) {
			sizecnt[own_segment[i].size()]++;
		}
	}
	// T - 2 条线段 
	// H - 3 条线段 
	// U - 3 条线段 
	// P - 4 条线段 
	// C - 3 条线段 
	// 那么就应该有:
	// 1 个大小为 2 的连通块 
	// 3 个大小为 3 的连通块 
	// 1 个大小为 4 的连通块 
	if (sizecnt[2] != 1 || sizecnt[3] != 3 || sizecnt[4] != 1) {
		printf("No");
		return 0;
	}
	// 处理 l, r, y 和 d, u, x 数组 
	for (int seg = 0; seg < cnt0 + cnt1; seg++) {
		if (horizontal(seg)) {
			l[seg] = res0[seg].l;
			r[seg] = res0[seg].r;
			y[seg] = res0[seg].y;
		} else {
			d[seg] = res1[seg - cnt0].d;
			u[seg] = res1[seg - cnt0].u;
			x[seg] = res1[seg - cnt0].x;
		}
	}
	// T!
	// 有没有找到 T
	bool T_is_ok = false;
	for (int i = 0; i < cnt0 + cnt1; i++) {
		if (fa[i] == i) {
			if (T(own_segment[i])) {
				T_is_ok = true;
				break;
			}
		}
	}
	if (!T_is_ok) {
		printf("No");
		return 0;
	}
	// P!
	// 有没有找到 P
	bool P_is_ok = false;
	for (int i = 0; i < cnt0 + cnt1; i++) {
		if (fa[i] == i) {
			if (P(own_segment[i])) {
				P_is_ok = true;
				break;
			}
		}
	}
	if (!P_is_ok) {
		printf("No");
	}
	// H & U & C!
	// 找到可能组成 H, U, C 的连通块 
	int now = 0;
	for (int i = 0; i < cnt0 + cnt1; i++) {
		if (fa[i] == i) {
			vector < int > & segments = own_segment[i];
			if (segments.size() == 3) {
				HUC[now] = i;
				now++;
			}
		}
	}
	// 下面还是枚举全排列 
	bool HUC_is_ok = false;
	sort(HUC, HUC + now);
	do {
		vector < int > & segments0 = own_segment[HUC[0]];
		vector < int > & segments1 = own_segment[HUC[1]];
		vector < int > & segments2 = own_segment[HUC[2]];
		if (H(segments0) && U(segments1) && C(segments2)) {
			HUC_is_ok = true;
			break;
		}
	} while (next_permutation(HUC, HUC + now));
	if (!HUC_is_ok) {
		printf("No");
		return 0;
	}
	// T, U, P, H, C 都找到了!
	printf("Yes");
	return 0;
}
2022/3/18 14:24