首页 > ACM题库 > HDU-杭电 > HDU 3902-Swordsman-图-[解题报告]HOJ
2015
04-14

HDU 3902-Swordsman-图-[解题报告]HOJ

Swordsman

问题描述 :

Mr. AC is a swordsman. His dream is to be the best swordsman in the world. To achieve his goal, he practices every day. There are many ways to practice, but Mr. AC likes “Perfect Cut” very much. The “Perfect Cut” can be described as the following two steps:
1.  Put a piece of wood block on the desk, and then suddenly wave the sword, cutting the block into two pieces.
2.  Without any motion, the two pieces must be absolutely axial symmetry.
According to the step two, when the board is an axial symmetry figure, Mr. AC has a chance to achieve the “Perfect Cut”. Now give you a board, and you should tell if Mr. AC has a chance to complete the “Perfect Cut”. The board is a simple polygon.

输入:

The input contains several cases.
The first line of one case contains a single integer n (3 <= n <= 20000), the number of points. The next n lines indicate the points of the simple polygon, each line with two integers x, y (0 <= x, y <= 20000). The points would be given either clockwise or counterclockwise.

输出:

The input contains several cases.
The first line of one case contains a single integer n (3 <= n <= 20000), the number of points. The next n lines indicate the points of the simple polygon, each line with two integers x, y (0 <= x, y <= 20000). The points would be given either clockwise or counterclockwise.

样例输入:

3
0 0
2 0
0 1
4
0 0
0 1
1 1
1 0

样例输出:

NO
YES
Hint
Huge input, scanf is recommended.

    判断二维平面上的一个图形是否是轴对称图形,图形的点按顺时针方向或者逆时针方向给出。直接判断的话,情况很多,很复杂。对称轴可能穿过图形中的一点,或者穿过相邻两点的中点。把图形中每相邻两点的中点加入进去,情况就变得非常简单了。假设原图有n个点,加入中点后就有2*n个点。如果图形是轴对称图形,那么对称轴肯定是穿过某x点和x+n点,这样只需要枚举x即可。时间复杂度虽然是O(n^2),但如果枚举直线x,x+n不是对称轴,大部分情况下很快就能排除。

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include <memory.h>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <iostream>
#include <sstream>

#define ll __int64

using namespace std;

const double eps = 1e-8;
const int maxn = 40005;

struct Point {
    double x, y;
} p[maxn];

int n;

double dis(int a, int b) {
    double dx = p[a].x - p[b].x;
    double dy = p[a].y - p[b].y;
    return sqrt(dx * dx + dy * dy);
}

bool Check(int a, int b) {
    int x = a - 1, y = a + 1;
    while (y != b) {
        if (x == -1) x = 2 * n - 1;
        if (fabs(dis(x, a) - dis(y, a)) > eps) return false;
        if (fabs(dis(x, b) - dis(y, b)) > eps) return false;
        x--, y++;
    }
    return true;
}

int main() {
    int i;
    while (scanf("%d", &n) != EOF) {
        for (i = 0; i < n; i++) {
            scanf("%lf %lf", &p[i*2].x, &p[i*2].y);
            if (i > 0) {
                p[i*2-1].x = (p[i*2].x + p[i*2-2].x) / 2.0;
                p[i*2-1].y = (p[i*2].y + p[i*2-2].y) / 2.0;
            }
        }
        p[n*2-1].x = (p[0].x + p[n*2-2].x) / 2.0;
        p[n*2-1].y = (p[0].y + p[n*2-2].y) / 2.0;
        
        for (i = 0; i < n; i++) {
            if (Check(i, i + n))
                break;
        }
        puts(i == n ? "NO" : "YES");
    }
    return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/racebug2010/article/details/6838360


,
  1. 算法是程序的灵魂,算法分简单和复杂,如果不搞大数据类,程序员了解一下简单点的算法也是可以的,但是会算法的一定要会编程才行,程序员不一定要会算法,利于自己项目需要的可以简单了解。

  2. 第23行:
    hash = -1是否应该改成hash[s ] = -1

    因为是要把从字符串s的start位到当前位在hash中重置

    修改提交后能accept,但是不修改居然也能accept