题目地址:http://acm.hdu.edu.cn/showproblem.php?pid=5258

题目描述

小度熊喜欢玩木棒。一天他在玩木棒的时候,发现一些木棒会形成长方形。小度熊可能是处女座吧,他只会将木棒横竖摆放,这样会形成很多长方形。现在给你一些横竖摆放的木棒,请你帮小度熊数一数形成了多少个长方形。

为了简化题目,一个木棒的端点不会在另一个木棒上,也就是说,木棒的端点不会在长方形上。

思路

坑爹,花了1小时20分钟搞出来,用的是暴力/搜索…

第一次是把每个木棍的交点求出来,实在无解,然后换了个思路。

由于题目只有横、竖两种木棍,那么我把横竖两种木棍分为两类,分别放在一起。

输入的时候,横的木棍需要横坐标处理,使横坐标小的放在x1,横坐标大的放在x2;竖的木棍需要纵坐标处理,使纵坐标小的放在y1, 纵坐标大的放在y2。

输入完毕后,对横竖木棍进行排序,横木棍集合纵坐标由大到小排序,竖木棍集合横坐标从小往大排序。

依次取出两根竖木棍,和两根横木棍进行判断,若能围成矩形则计数。

AC代码

/*************************************************************************
    > File Name: 602_1001.cpp
      > Author: Netcan
      > Blog: http://www.netcan.xyz
      > Mail: 1469709759@qq.com
      > Created Time: Sat 06 Jun 2015 03:44:46 PM CST
 ************************************************************************/

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <sstream>
#include <deque>
#include <functional>
#include <iterator>
#include <list>
#include <map>
#include <memory>
#include <stack>
#include <set>
#include <numeric>
#include <utility>
#include <cstring>
using namespace std;
struct l {
    int x1, x2, y1, y2;
} l1[30],l2[30]; // 竖, 横

bool cmp1(const l &a, const l &b) { // 竖木棍横坐标从小到大排序
    return a.x1 < b.x1;
}
bool cmp2(const l &a, const l &b) { // 横木棍纵坐标从大到小排序
    return a.y1 > b.y1;
}

int main()
{
#ifdef Oj
    freopen("602_1001.in", "r", stdin);
#endif
    int T;
    cin >> T;
    int Case = 1;
    while(T--) {
        int n;
        cin >> n;
        int lc1=0, lc2=0; // 竖、横木棍个数
        int x1, x2, y1, y2;
        for (int i = 0; i < n; ++i) {
            cin >> x1 >> y1 >> x2 >> y2;
            if(x1 == x2) { // 竖木棍
                l1[lc1].x1 = l1[lc1].x2 = x1;
                l1[lc1].y1 = min(y1, y2); // 纵坐标小的放在y1,大的放在y2
                l1[lc1].y2 = max(y1, y2);
                ++lc1;
            }
            else { // 横木棍
                l2[lc2].y1 = l2[lc2].y2 = y1;
                l2[lc2].x1 = min(x1, x2); // 横坐标小的放在x1,大的放在x2
                l2[lc2].x2 = max(x1, x2);
                ++lc2;
            }
        }
        sort(l1, l1+lc1, cmp1); // 竖木棍集合横坐标从小往大排序
        sort(l2, l2+lc2, cmp2); // 横木棍纵坐标从大到小排序
        int counts = 0; // 矩形个数

        for(int i=0; i<lc1; ++i) {
            for(int j=i+1; j<lc1; ++j) { //  竖木棍i, j
                for(int k=0; k<lc2; ++k)  {
                    for(int m=k+1; m<lc2; ++m) { // 横木棍k, m
                        if(l2[k].y1 <= min(l1[i].y2, l1[j].y2) && 
                        l2[m].y1 >= max(l1[i].y1, l1[j].y1) && 
                        l1[i].x1 >= max(l2[k].x1, l2[m].x1) && 
                        l1[j].x2 <= min(l2[k].x2, l2[m].x2))
                            ++counts;
                    }

                }
            }
        }
        printf("Case #%d:\n", Case++);
        cout << counts << endl;
    }
    return 0;
}