首页 > 代码库 > POJ 1859 The Perfect Symmetry && POJ2526 Center of symmetry(思维题)

POJ 1859 The Perfect Symmetry && POJ2526 Center of symmetry(思维题)

博客原文地址:http://blog.csdn.net/xuechelingxiao/article/details/40680981


POJ 1859 : The Perfect Symmetry


题目大意:

给你n个点的座标,你的任务是判断是否存在一个中心,使得这些点中心对称。一个点集有中心对称点的条件是,存在一个点s,对于每一个点p,都存在另一个点q使得p - s = s - q 。


解题思路:

既然要找中间的点,那么对于中间的点,肯定会有两边对称的点,那么说,点集排序之后,先找到排序后的第一个点跟最后一个点,求出一个中心,循环从前面取一个点,从后面取一个点,在求一个中心,若两个中心吻合,则可以继续取,若不吻合,就是没有中心。


具体的看代码就好了

#include <stdio.h>
#include <iostream>
#include <algorithm>
using namespace std;

struct Point {
    double x, y;
} P[20010], o;

int cmp(Point a, Point b) {
    if(a.x == b.x)
        return a.y < b.y;
    return a.x < b.x;
}

int main()
{
    int n;
    while(~scanf("%d", &n) && n) {
        bool flag = true;
        for(int i = 1; i <= n; ++i) {
            scanf("%lf%lf", &P[i].x, &P[i].y);
        }
        sort(P+1, P+n+1, cmp);
        o.x = (P[1].x+P[n].x)/2;
        o.y = (P[1].y+P[n].y)/2;
        for(int i = 2; i <= n; ++i) {
            double x = (P[i].x+P[n-i+1].x)/2;
            double y = (P[i].y+P[n-i+1].y)/2;
            if(x != o.x || y != o.y) {
                flag = false;
                //printf("%d\n", i);
                break;
            }
        }
        if(flag) {
            printf("V.I.P. should stay at (%.1lf,%.1lf).\n", o.x, o.y);
        }
        else {
            printf("This is a dangerous situation!\n");
        }
    }

    return 0;
}
POJ 2526 :Center of symmetry
#include <stdio.h>
#include <iostream>
#include <algorithm>
using namespace std;

struct Point {
    double x, y;
} P[20010], o;

int cmp(Point a, Point b) {
    if(a.x == b.x)
        return a.y < b.y;
    return a.x < b.x;
}

int main()
{
    int n;
    int T;
    scanf("%d", &T);
    while(T--) {
        bool flag = true;
        scanf("%d", &n);
        for(int i = 1; i <= n; ++i) {
            scanf("%lf%lf", &P[i].x, &P[i].y);
        }
        sort(P+1, P+n+1, cmp);
        o.x = (P[1].x+P[n].x)/2;
        o.y = (P[1].y+P[n].y)/2;
        for(int i = 2; i <= n; ++i) {
            double x = (P[i].x+P[n-i+1].x)/2;
            double y = (P[i].y+P[n-i+1].y)/2;
            if(x != o.x || y != o.y) {
                flag = false;
                //printf("%d\n", i);
                break;
            }
        }
        if(flag) {
            printf("yes\n");
        }
        else {
            printf("no\n");
        }
    }

    return 0;
}




POJ 1859 The Perfect Symmetry && POJ2526 Center of symmetry(思维题)