hihoCoder 1552-缺失的拼图
#1552 : 缺失的拼图
时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
小Hi在玩一个拼图游戏。如下图所示，整个拼图是由N块小矩形组成的大矩形。现在小Hi发现其中一块小矩形不见了。给定大矩形以及N-1个小矩形的顶点坐标，你能找出缺失的那块小矩形的顶点坐标吗？
输入
第一行包含一个整数，N。 第二行包含四个整数，(X0, Y0), (X‘0, Y‘0)，代表大矩形左下角和右上角的坐标。 以下N-1行每行包含四个整数，(Xi, Yi), (X‘i, Y‘i)，代表其中一个小矩形的左下角和右上角坐标。 对于30%的数据， 1 <= N <= 1000 对于100%的数据，1 <= N <= 100000 所有的坐标(X, Y)满足 0 <= X, Y <= 100000000输出
输出四个整数(X, Y), (X‘, Y‘)代表缺失的那块小矩形的左下角和右上角的坐标。- 样例输入
-
5 0 0 4 5 0 0 3 1 0 1 2 5 3 0 4 5 2 2 3 5
- 样例输出
-
2 1 3 2
一个矩形由N个小矩形拼接而成，现在丢了一个小矩形，怎样才能找到这个小矩形呢。所有矩形都用左下角坐标和右上角坐标表示。 这一题也很有意思，丢掉的那个小矩形的坐标肯定是其他N-1个矩形的坐标中的某4个。我们可以统计每个坐标点出现的次数，如果出现偶数次，则这个点所在的矩形是出现过的，否则这个点就是缺失矩形的某个顶点。最后，从缺失的4个顶点中找出左下角坐标和右上角坐标。 完整代码如下： [cpp] #include<algorithm> #include<vector> #include<iostream> #include<unordered_map> #include<unordered_set> #include<string> #include<set> #include<map> #include<queue> using namespace std; typedef long long ll; typedef pair<int, int> Point; int main() { //freopen("input.txt", "r", stdin); int n; scanf("%d", &n); map<Point, int> hash; int a, b, c, d; while (n–) { Point left_bottom, right_top; scanf("%d %d %d %d", &left_bottom.first, &left_bottom.second, &right_top.first, &right_top.second); Point left_top = Point(left_bottom.first, right_top.second), right_bottom = Point(right_top.first, left_bottom.second); ++hash[left_bottom]; ++hash[right_top]; ++hash[left_top]; ++hash[right_bottom]; } set<Point> ans; for (auto p : hash) { if (p.second % 2 == 1) { ans.insert(p.first); } } a = c = ans.begin()->first; b = d = ans.begin()->second; for (auto p : ans) { a = min(a, p.first); b = min(b, p.second); c = max(c, p.first); d = max(d, p.second); } printf("%d %d %d %d\n", a, b, c, d); return 0; } [/cpp] 本代码提交AC，用时432MS。]]>