b604: Center of Symmetry

2019-08-20

內容

Given a set of n points in a plane with integer coordinates (xi, yi), i = 1, 2, . . . , n. Your task is to decide whether the set of points has a center of symmetry or not.

A set of points S has a center of symmetry if there exists a point s (not necessarily in S) such that for every point p in S there exists a point q in S such that p - s = s - q.

輸入

For each case, the first line contains a number n, 1 <= n <= 10000. The subsequent n

lines contain two integers, which are the x and y coordinates of the point. Every point is unique and -10000000 <= x, y <= 10000000. A line with 0 (n = 0) signifies the end of input. A figure shown below is the sample input.

8
1 10
3 6
6 8
6 2
3 -4
1 0
-2 -2
-2 4
0

輸出

For each set of input data print “yes” if the set of points has a center of symmetry and “no” otherwise.

yes

解題思路

題目大概的意思是 : 給你 n 個點，所有的點是否都有另一個對稱於中心的點存在。

先找出中心點，取所有點至中心點的距離，如果距離有不成對的 (沒有和他一樣的) 情況就代表他沒有對稱於中心的另一個點。

因為沒有要用於計算，距離取曼哈頓距離就行了。

完整程式碼

AC (12ms, 552KB)

#include <stdio.h>
#include <stdlib.h>
#define ABS(x) ((x) < 0 ? -(x) : (x))

typedef struct node
{
    double x, y;
}Point;

Point pList[10000];

int cmp(const Point* lhs, const Point* rhs)
{
    return lhs->x - rhs->x;
}

int main()
{
    int n, pLen;
    char allPair;
    while (scanf(" %d", &n) == 1 && n)
    {
        Point midPoint = { 0 };
        pLen = 0, allPair = 1;
        for (int i = 0; i < n; i++)
        {
            scanf(" %lf %lf", &pList[pLen].x, &pList[pLen].y);
            midPoint.x += pList[pLen].x;
            midPoint.y += pList[pLen++].y;
        }
        midPoint.x /= n, midPoint.y /= n;
        for (int i = 0; i < n; i++)
            pList[i].x = ABS(pList[i].x - midPoint.x) + ABS(pList[i].y - midPoint.y);
        qsort(pList, n, sizeof(Point), cmp);
        for (int i = 1; i < n; i += 2)
        {
            if (pList[i].x != pList[i - 1].x)
            {
                allPair = 0;
                break;
            }
        }
        puts(allPair ? "yes" : "no");
    }
    return 0;
}