时间戳

首页 > 解决方案 > 查找矩形的缺失坐标

algorithm - 查找矩形的缺失坐标

问题描述

Chef 在 2D 笛卡尔坐标系中有 N 个轴平行的矩形。这些矩形可能相交，但可以保证它们的所有 4N 个顶点都是成对不同的。

不幸的是，Chef 丢失了一个顶点，直到现在，他的修复都没有奏效（尽管在牛奶盒上放一个点的图像可能并不是最好的主意……）。因此，他给了你寻找它的任务！给你剩下的 4N−1 个点，你应该找到丢失的点。

输入 输入的第一行包含一个整数 T，表示测试用例的数量。T 测试用例的描述如下。每个测试用例的第一行包含一个整数 N。然后是 4N-1 行。这些行中的每一行都包含两个以空格分隔的整数 x 和 y，表示某个矩形的顶点 (x,y)。输出 对于每个测试用例，打印一行，其中包含两个空格分隔的整数 X 和 Y——缺失点的坐标。可以证明缺失点可以唯一确定。

约束条件 T≤100 1≤N≤2⋅105 |x|,|y|≤109 所有测试用例的 N 总和不超过 2⋅105 示例输入 1 2 1 1 1 2 4 6 2 1 9 6 9 3 4 3 示例输出 2 2

问题链接：https ://www.codechef.com/problems/PTMSSNG

我的方法：我为 x 和 y 坐标创建了一个频率数组，然后计算出奇数点。次。

    #include <iostream>
using namespace std;

int main() {
    // your code goes here
    int t;
    cin>>t;
    while(t--)
    {
        long int n;
        cin>>n;
        long long int a[4*n-1][2];
        long long int xm,ym,x,y;
        for(int i=0;i<4*n-1;i++)
        {
            cin>>a[i][0]>>a[i][1];
            if(i==0)
            {
                xm=abs(a[i][0]);
                ym=abs(a[i][1]);
            }
            if(i>0)
            {
                if(abs(a[i][0])>xm)
                {
                    xm=abs(a[i][0]);
                }
                if(abs(a[i][1])>ym)
                {
                    ym=abs(a[i][1]);
                }
            }
        }
        long long int frqx[xm+1],frqy[ym+1];
        for(long long int i=0;i<xm+1;i++)
        {
            frqx[i]=0;
        }
        for(long long int j=0;j<ym+1;j++)
        {
            frqy[j]=0;
        }
        for(long long int i=0;i<4*n-1;i++)
        {
            frqx[a[i][0]]+=1;
            frqy[a[i][1]]+=1;
        }
        for(long long int i=0;i<xm+1;i++)
        {
            if(frqx[i]>0 && frqx[i]%2>0)
            {
                x=i;
                break;
            }
        }
        for(long long int j=0;j<ym+1;j++)
        {
            if(frqy[j]>0 && frqy[j]%2>0)
            {
                y=j;
                break;
            }
        }
        cout<<x<<" "<<y<<"\n";
    }
    return 0;
}

我的代码显示输入的 TLE <10^6

标签： algorithmc++11

解决方案

我发现@Ext3h 关于错误的答案是足够的。

解决方案，如果你遇到问题的奇/偶质量，可以更直接地完成。

您需要找到出现奇数次的 x 和 y。

在java中

int[] missingPoint(int[][] a) {
    //int n = (a.length + 1) / 4;

    int[] pt = new int[2]; // In C initialize with 0.
    for (int i = 0; i < a.length; ++i) {
        for (int j = 0; j < 2; ++j) {
            pt[j] ^= a[i][j];
        }
    }
    return pt; 
}

这使用异或^，它是关联和自反的 0^x=x, x^x=0。(5^7^4^7^5=4.) 对于这些“搜索奇数”，可以使用此异或运算。

实际上，您不需要将输入保存在数组中。

推荐阅读