題目

題目.png

Paste_Image.png

Paste_Image.png

分析

題目是要求檢測互相之間有碰撞的矩形的個數(shù)，怎么確定兩個矩形之間是否有碰撞呢？
我的思路如下，任給定兩個矩形，根據(jù)其左上角坐標(biāo)和右下角坐標(biāo)，計(jì)算出其中心坐標(biāo)（x0, y0）,
其寬度 Width = | x1 - x2 |，其高度 Height = | y1 - y2 |，如果：
兩矩形中心坐標(biāo)X的差值小于 等于它們寬度之和的一半， 且 兩矩形中心坐標(biāo)的Y的差值小于等于它們高度之和的一半, 那么則判定兩矩形相交。

怎么統(tǒng)計(jì)出所有的相交個數(shù)呢？我使用了很直接的思路，兩兩矩形逐個檢測。

沒有去想太好的辦法，如果有更好的解決辦法，希望各位積極指教！

代碼如下：

#include <iostream>
#include <cmath>
#include <vector>

using namespace std;

class Point
{
public:
    Point() { }
    Point(float _x, float _y)
        : x(_x), y(_y) { }

    float x, y;
};

struct Rect
{
    Rect(float x1, float y1, float x2, float y2)
        : Width( std::abs(x2 - x1) )
        , Height( std::abs(y2 - y1) )
        , TopLeft( Point(x1, y1) )
        , RightBottom( Point(x2, y2) )
        , Center( Point( (x1 + x2) / 2,  (y1 + y2) / 2 ) )
    {   }

    float Width, Height;

    Point TopLeft, RightBottom, Center;
};

// 碰撞檢測
int CollisionDection(const std::vector<Rect>& rects)
{
    std::size_t Size = rects.size();
    int Counter = 0;

    for (int i = 0; i < Size - 1; ++i) {
        for (int j = i + 1; j < Size; ++j) {
            Rect r1 = rects.at(i);
            Rect r2 = rects.at(j);
            if (std::abs(r1.Center.x - r2.Center.x) <= (r1.Width + r2.Width) / 2
                    && std::abs(r1.Center.y - r2.Center.y) <= (r1.Height + r2.Height) / 2)
                Counter++;
        }
    }

    return Counter;
}

int main(void)
{
    int t;
    std::cin >> t;

    while(t--)
    {
        int n;
        std::cin >> n;
        std::vector<Rect> Rects;

        while (n--)
        {
            float x1, x2, y1, y2;
            std::cin >> x1 >> y1 >> x2 >> y2;
            Rects.push_back(Rect(x1, y1, x2, y2));
        }
        std::cout << CollisionDection(Rects) << std::endl;
    }
}