2 条题解

  • 4
    @ 2022-5-27 17:09:05

    本题做法就是暴力枚举,因为数据范围都比较小。可以尝试这个操作。

    暴力枚举当然是一次性枚举4个点的坐标,然后判断这4个点能否构成矩形,同时判断是否可以平行坐标轴即可。

    首先题目说了有可能有重复的点,那我们需要排序后去重,同时排序也是为了方便我们枚举4个点。

    排序去重应该很好理解,按照xx进行排序,xx相等按照yy排序,都是从小到大。

    struct node
    {
    	int x, y;
    } a[55];
    vector<node> v;
    bool cmp(node x, node y)
    {
    	if (x.x != y.x)
    		return x.x < y.x;
    	return x.y < y.y;
    }
    for (int i = 1; i <= n; i++)
    	cin >> a[i].x >> a[i].y;
    sort(a + 1, a + n + 1, cmp);
    v.push_back(a[1]);
    for (int i = 2; i <= n; i++)
    {
    	if (a[i].x != a[i - 1].x || a[i].y != a[i - 1].y)
    		v.push_back(a[i]);
    }
    

    然后开始4个循环暴力枚举,如何判断4个点能否构成矩形,根据我们排序后的坐标,选取4个坐标一定是满足如下条件。

    x1<=x2<=x3<=x4x_1<=x_2<=x_3<=x_4,

    y1<=y2<=y3<=y4y_1<=y_2<=y_3<=y_4,

    假设这4个点已经可以构成矩形,

    那么它们一定是这个样子。

    Xm35V0.png

    所以我们根据初中学的几何知识,对角线相等的一定是矩形,也就是 dist(a[1],a[4])==dist(a[2],a[3])dist(a[1],a[4])==dist(a[2],a[3])

    接下来继续搞定它何时可以垂直坐标轴,那么显然

    a[1].x==a[2].x,a[1].y==a[3].y,a[3].x==a[4].xa[1].x==a[2].x,a[1].y==a[3].y,a[3].x==a[4].x即可。

    #include <bits/stdc++.h>
    using namespace std;
    int t, n, ans;
    struct node
    {
        int x, y;
    } a[55];
    vector<node> v;
    bool cmp(node x, node y)
    {
        if (x.x != y.x)
            return x.x < y.x;
        return x.y < y.y;
    }
    long long dist(node x, node y)
    {
        return (x.x - y.x) * (x.x - y.x) + (x.y - y.y) * (x.y - y.y);
    }
    int main()
    {
        ios::sync_with_stdio(false);
        cin.tie(0);
        cin >> t;
        while (t--)
        {
            cin >> n;
            ans = 0;
            v.clear();
            for (int i = 1; i <= n; i++)
                cin >> a[i].x >> a[i].y;
            sort(a + 1, a + n + 1, cmp);
            v.push_back(a[1]);
            for (int i = 2; i <= n; i++)
            {
                if (a[i].x != a[i - 1].x || a[i].y != a[i - 1].y)
                    v.push_back(a[i]);
            }
            for (int i = 0; i < v.size() - 3; i++)
            {
                for (int j = i + 1; j < v.size() - 2; j++)
                {
                    for (int k = j + 1; k < v.size() - 1; k++)
                    {
                        for (int w = k + 1; w < v.size(); w++)
                        {
                            if (dist(v[i], v[w]) == dist(v[j], v[k]) && (v[i].y == v[k].y) && (v[i].x == v[j].x) && (v[k].x == v[w].x))
                            {
                                ans++;
                            }
                        }
                    }
                }
            }
            cout << ans << "\n";
        }
        return 0
    
    • -3
      @ 2022-4-24 16:41:43

      写题解请注意

      鼓励大家写题解,但注意题解格式。

      题解一定要有思路解析或代码注释,能否让别人理解你的思路

      也是你的能力的检验,不要只放无意义的代码给大家复制,那就失去了做题的初心。

      给代码两端加上这个会舒服一些

      ```cpp

      你的代码

      ```

      </span>

      这个点在键盘的左上角tab上面那个键,注意切换输入法

      #include<iostream>
      using namespace std;
      int main()
      {
          int n;
          cin>>n;//这是一个注释
          return 0;
      } 
      

      请注意严禁抄袭题解,写题解不要只放代码,需加上你的思路或代码注释。

      抄袭题解一经发现直接取消成绩。

      题解被删除的可能

      1. 代码不符合格式规范
      2. 没有思路讲解或者没有注释,
      3. 无意义的题解

      大家携手共同维护一个良好的编程环境,如果一经发现,多次作乱。可能会被管理员拉黑,请注意,一旦拉黑即失去登陆资格。

      • 1

      信息

      ID
      193
      时间
      1000ms
      内存
      256MiB
      难度
      7
      标签
      递交数
      347
      已通过
      82
      上传者