hihocoder-1552-缺失的拼图

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')代表缺失的那块小矩形的左下角和右上角的坐标。

样例输入

样例输出

2 1 3 2

解法：

参考了 http://hihocoder.com/contest/offers22/solution/1148537 的answer。

原理在于：对于一个平面上的所有 rectangle，因为本题目中一定存在着一个空位是缺失的rectangle。所以，计算每一个存在的rectangle的四个点。将这些点进行汇总，一个点存在，一定会有一个或者三个另外的 rectangle 的点和这个点重合。所以，每一个点的 count 必定是偶数。

#include <cstdio> 
#include <cstring>
#include <iostream> 
#include <map> 
#include <vector> 
#include <algorithm> 
using namespace std; 

int main(){
    int n, x0, x1, y0, y1; 
    while(scanf("%d", &n) != EOF){
        map<pair<int,int>, int> mp; 
        for(int i=0; i<n; ++i){
            scanf("%d %d %d %d", &x0, &y0, &x1, &y1); 
            mp[ make_pair(x0, y0) ]++; 
            mp[ make_pair(x0, y1) ]++; 
            mp[ make_pair(x1, y0) ]++; 
            mp[ make_pair(x1, y1) ]++; 
        }

        vector<int> Xod, Yod; 
        for(map<pair<int,int>, int>::iterator i = mp.begin(); i!= mp.end(); ++i ){
            if(i->second % 2 != 0){
                Xod.push_back( (i->first).first ); 
                Yod.push_back( (i->first).second ); 
            } 
        }

        sort(Xod.begin(), Xod.end()); 
        sort(Yod.begin(), Yod.end()); 

        printf("%d %d %d %d
", Xod[0], Yod[0], Xod[3], Yod[3] );
    }
    return 0; 
}