卡车停车场围栏长度计算问题题解

一、题目分析

题目要求根据给定的柱子坐标计算围栏长度。围栏由南北和东西方向的线段组成，柱子仅位于方向改变的拐点处。关键点在于：

• 围栏是闭合的多边形，边均为水平或垂直方向。
• 柱子坐标唯一，且相邻拐点间的边为水平或垂直线段。

二、算法思路

围栏的总长度可分解为水平边长度总和与垂直边长度总和之和。通过以下步骤计算：

1. 垂直边长度计算：

   • 将所有点按x坐标排序，x相同的点按y排序。
   • 相邻且x坐标相同的点构成垂直边，边长为y坐标差。由于围栏闭合，每段垂直边会被两个相邻点对各计算一次，因此只需累加相邻点对的y差。

2. 水平边长度计算：

   • 将所有点按y坐标排序，y相同的点按x排序。
   • 相邻且y坐标相同的点构成水平边，边长为x坐标差。同理，每段水平边会被两个相邻点对各计算一次，累加相邻点对的x差。

三、代码实现

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
#define INF (1<<29)
#define maxn 100005
struct node
{
    int x,y;
}num[maxn];
int n;
int cmp1(node a,node b)
{
    if(a.x==b.x)
        return a.y<b.y;
    return a.x<b.x;
}
int cmp2(node a,node b)
{
    if(a.y==b.y)
        return a.x<b.x;
    return a.y<b.y;
}
int main()
{
    while(scanf("%d",&n),n)
    {
        for(int i=0;i<n;i++)
            scanf("%d%d",&num[i].x,&num[i].y);
        int ans=0;//初始化 
        sort(num,num+n,cmp2);//按纵坐标升序排 
        for(int i=0;i<n;i+=2)   
            ans+=num[i+1].x-num[i].x;//累加纵坐标相同两点间距 
        sort(num,num+n,cmp1);//按横坐标升序排 
        for(int i=0;i<n;i+=2)
            ans+=num[i+1].y-num[i].y;;//累加横坐标相同两点间距 
        printf("The length of the fence will be %d units.\n",ans);  
    }
    return 0;
}

四、代码解释

1. 输入处理：循环读取每个数据块，直到n=0时终止。
2. 垂直边计算：
   • 按x坐标排序后，遍历相邻点对，若x相同则累加y坐标差。由于闭合多边形中每条垂直边会被两个相邻点对（正序和逆序）各计算一次，此处仅需计算一次相邻差。
3. 水平边计算：
   • 按y坐标排序后，同理遍历相邻点对，累加x坐标差。
4. 结果输出：垂直边与水平边长度之和即为围栏总长度。

五、复杂度分析

• 排序复杂度：两次排序均为O(n log n)，n为点数。
• 遍历复杂度：两次遍历均为O(n)。
• 总复杂度：O(n log n)，适用于n≤1e5的数据规模。

该算法通过坐标排序和相邻点对分析，巧妙地将围栏长度分解为水平和垂直方向的累加，确保了正确性和高效性。

#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=100000+10;
struct Point
{
    int x,y;
}P[maxn];
bool compare_x(Point A,Point B)//升序排列
{
    return A.x<B.x || (A.x==B.x&&A.y<B.y);
}
bool compare_y(Point A,Point B)
{
    return A.y<B.y || (A.y==B.y&&A.x<B.x);
}
 
 
int main()
{
    int n;
    while(scanf("%d",&n)==1 && n)
    {
        for(int i=0;i<n;++i) scanf("%d%d",&P[i].x,&P[i].y);
        int ans=0;
        sort(P,P+n,compare_x);
        for(int i=0;i<n;)
        {
            if(P[i].x==P[i+1].x)//计算竖直边
            {
                ans += P[i+1].y-P[i].y;
                i+=2;
            }
            else ++i;
        }
        sort(P,P+n,compare_y);
        for(int i=0;i<n;)
        {
            if(P[i].y==P[i+1].y)//计算水平边
            {
                ans+= P[i+1].x-P[i].x;
                i+=2;
            }
            else ++i;
        }
        printf("The length of the fence will be %d units.\n",ans);
    }
    return 0;
}