E-构成正方形的数量(100p)

刷题笔记合集🔗

构成正方形的数量

问题描述

给定 个互不相同的二维整数坐标点,求这 个坐标点可以构成的正方形数量。需要注意的是,两个向量的内积为零时,这两个向量垂直。

输入格式

第一行输入一个正整数 ,表示坐标点的数量。

接下来的 行,每行包含两个整数 ,以空格分隔,表示一个坐标点

输出格式

输出一个整数,表示可以构成的正方形数量。

样例输入1

3
1 3
2 4
3 1

样例输出1

0

样例输入2

4
0 0
1 2
3 1
2 -1

样例输出2

1

样例解释

样例 解释说明
样例1 3个点不足以构成正方形,因此输出0。
样例2 4个点可以构成1个正方形,因此输出1。

数据范围

题解

这道题目要求我们计算给定的 个点中可以构成的正方形数量。解决这个问题的关键在于理解正方形的性质和如何利用坐标系中的点来判断正方形。

首先,我们需要明白,一个正方形可以由任意两个点确定。当我们知道正方形的一条边(即两个点的坐标)时,我们就可以计算出其他两个点的坐标。

解题思路如下:

  1. 枚举任意两个点作为正方形的一条边。
  2. 根据这两个点,计算出可能的其他两个点的坐标。
  3. 检查计算出的点是否在给定的点集中。
  4. 如果所有四个点都在点集中,则找到了一个正方形。

参考代码

  • Python
def count_squares(points):
    # 将点集转换为集合,方便快速查找
    point_set = set(points)
    n = len(points)
    count = 0

    # 枚举所有可能的点对
    for i in range(n):
        for j in range(i + 1, n):
            x1, y1 = map(int, points[i].split())
            x2, y2 = map(int, points[j].split())
            
            # 计算第一组可能的正方形点
            x3 = x1 - (y1 - y2)
            y3 = y1 + (x1 - x2)
            x4 = x2 - (y1 - y2)
            y4 = y2 + (x1 - x2)
            
            # 检查这两个点是否在点集中
            if f"{x3} {y3}" in point_set and f"{x4} {y4}" in point_set:
                count += 1

            # 计算第二组可能的正方形点
            x5 = x1 + (y1 - y2)
            y5 = y1 - (x1 - x2)
            x6 = x2 + (y1 - y2)
            y6 = y2 - (x1 - x2)
            
            # 检查这两个点是否在点集中
            if f"{x5} {y5}" in point_set and f"{x6} {y6}" in point_set:
                count += 1

    # 由于每个正方形被计算了4次,所以需要除以4
    return count // 4

# 读取输入
n = int(input())
points = [input() for _ in range(n)]

# 计算并输出结果
result = count_squares(points)
print(result)
  • C
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// 定义点的最大数量
#define MAX_POINTS 1000
// 定义单个点的字符串长度 (例如 "123 456")
#define MAX_POINT_LEN 20

// 字符串集合结构体
typedef struct {
    char points[MAX_POINTS][MAX_POINT_LEN]; // 存储点的字符串
    int size; // 集合中的点数量
} PointSet;

// 初始化点集合
void initPointSet(PointSet *set) {
    set->size = 0;
}

// 向点集合中添加一个点
void addPoint(PointSet *set, const char *point) {
    strcpy(set->points[set->size], point);
    set->size++;
}

// 检查集合中是否包含指定的点
int containsPoint(PointSet *set, const char *point) {
    for (int i = 0; i < set->size; i++) {
        if (strcmp(set->points[i], point) == 0) {
            return 1; // 找到匹配的点
        }
    }
    return 0; // 未找到匹配的点
}

// 计算可能的正方形数量
int countSquares(char points[MAX_POINTS][MAX_POINT_LEN], int n) {
    PointSet pointSet;
    initPointSet(&pointSet);

    // 将所有点添加到集合中
    for (int i = 0; i < n; i++) {
        addPoint(&pointSet, points[i]);
    }

    int count = 0;

    // 遍历所有可能的点对 (i, j)
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            int x1, y1, x2, y2;
            sscanf(points[i], "%d %d", &x1, &y1); // 从第一个点获取坐标
            sscanf(points[j], "%d %d", &x2, &y2); // 从第二个点获取坐标

            // 计算第一组可能的正方形点
            int x3 = x1 - (y1 - y2);
            int y3 = y1 + (x1 - x2);
            int x4 = x2 - (y1 - y2);
            int y4 = y2 + (x1 - x2);

            // 构造两个点的字符串表示
            char p3[MAX_POINT_LEN], p4[MAX_POINT_LEN];
            snprintf(p3, MAX_POINT_LEN, "%d %d", x3, y3);
            snprintf(p4, MAX_POINT_LEN, "%d %d", x4, y4);

            // 检查这两个点是否存在于集合中
            if (containsPoint(&pointSet, p3) && containsPoint(&pointSet, p4)) {
                count++;
            }

            // 计算第二组可能的正方形点
            int x5 = x1 + (y1 - y2);
            int y5 = y1 - (x1 - x2);
            int x6 = x2 + (y1 - y2);
            int y6 = y2 - (x1 - x2);

            // 构造第二组两个点的字符串表示
            char p5[MAX_POINT_LEN], p6[MAX_POINT_LEN];
            snprintf(p5, MAX_POINT_LEN, "%d %d", x5, y5);
            snprintf(p6, MAX_POINT_LEN, "%d %d", x6, y6);

            // 检查这两个点是否存在于集合中
            if (containsPoint(&pointSet, p5) && containsPoint(&pointSet, p6)

剩余60%内容,订阅专栏后可继续查看/也可单篇购买

算法刷题笔记 文章被收录于专栏

本专栏收集并整理了一些刷题笔记

全部评论
有需要的宝子可以订阅专栏哦~
点赞 回复 分享
发布于 10-31 11:56 浙江

相关推荐

刚刚做了华为Java机考,人是懵的。三道题两小时,每道题都看着不难都有思路结果写完过了测试一提交只有10%通过率,最后只有第一题提到了85%,最后算下来135分过不了150线,我愧对期待值拉满的HR,愧对我自己的复习。。。还是没刷够和基础不足,但至少把题目发这里大伙帮我解决一下这个遗憾吧。(不是,哥们。发现十拿九稳的主思路只能过10%,真得懵吧)第一题100:游客参观总时长问游乐园每天开放多久能招待所有游客。游乐园每一段时间能接受任意个数游客。每一行给一个游客的参观时长[1,5],[1,2],&nbsp;[10,11],输出总时长&nbsp;4+1=5.&nbsp;数值全在10^6以下。(确认输入无误)我一开始想做合并时间段最后算累加,结果Arraylist写下来边界判断什么的瞎闹连测试案例都过不了。三道题都写完之后回来检查,改了方法,求出参观时长的最大值,以它为长度建立空数组,再遍历游客时间插入1.最后数1,数到0就断掉算长度累加。通过率到了85%,但是给的反馈是测试用例运行错误,不是超时,我就只能继续检查下一题去了。(没想到后续检查没救得了我)第二题200:字符串集合求交集(这个是我最懵的,教教)(不需要检查输入)题目意思非常简单,给你输入几个字符串集合,{3(长度)&nbsp;123&nbsp;456&nbsp;789}第一个集合.{&nbsp;2&nbsp;456&nbsp;789}第二个集合。输出每个集合交集最大的集合和长度&nbsp;2&nbsp;2&nbsp;\n&nbsp;1&nbsp;2&nbsp;。字符串完全相等就是交集的元素。就这么简单。&nbsp;我Hashmap存集合的输入顺序,也就是集合的序号,value存的是字符串ArrayList。然后按总输出的值遍历这个输入顺序下标获取那个字符串集合,然后和另一个下标对应的字符串集合遍历。四层遍历求个相等的情况+1,记录最长值和最长集合序号。过了测试例以后提交,10%,还是答案错误不是超时,我人懵了,回来检查的时候也还是懵的。各路大神务必教教我这必须查相等的遍历为什么过了基础例子然后只能过10%的测试。有什么优化办法能既考虑边界值也能简化时长的?第三题300:摘水果也蛮直白的,给你个正方形地图,然后每个格子上是水果的数量,如果不能走就是-1.&nbsp;果农要从左上角走到右下角,只能向下或向右。走到右下角以后他再从右下角折回来走(没限制怎么走回来)到左上角,问你他能采摘的最大水果数量。这题我承认肯定是算法没想明白,漏了什么很关键的东西。(应该早点放弃检查的,很烦)这题我一开始想搞个递归往下找记录总数改变地图数字,然后往上找再递归找路最后加起来。但是写出来了向下找路然后发现这个找路和求最大值的路想做复原太诡异了,(现在想想完全可以找到路了记下来再找到最大值,很有可能能避免一些case)就放弃了递归投向动态规划。我累加了一次dp所有值抵达右下角以后,发现这个格子里的值正好是走下去走上来能拿到的最大值,想了一下应该也对,如果从左上角走不下来,那也不可能从那条路折回来,所有通路值加到最后应该就是答案。(难道说!是多个通路,只能取2条最大?!状态转移没这么简单才对!)状态转移方程就是等于非-1的左侧和上侧的格子的值相加再加上本来格子里的值。如果左上都是-1那我直接设为0.(难道该设为-1?复盘才发现槽点太多)(给地图加了一行一列全设为0,从1开始遍历到n。)往回走也不可能走这里。最后得分10%。求解!
牛客141057821号:我用python做的 第一道题记得leetcode有原题,先用开始参观时间sort一下然后指针遍历求set union 第二道题我python暴力解法全过。。 第三道题我是两遍dp,已从从左上到右下一次右下到左上,中间把第一次遍历走过的格子设成0就完了。 话说150是分数线吗?可以问下哪里的消息么
查看3道真题和解析 投递华为等公司10个岗位
点赞 评论 收藏
分享
1 2 评论
分享
牛客网
牛客企业服务