Project Euler 292 Pythagorean Polygons

Posted on | | 阅读数 次
Words count in article: 902 | Reading time ≈ 4

开启传送门

题目描述

We shall define a pythagorean polygon to be a convex polygon with the following properties:

  • there are at least three vertices,
  • no three vertices are aligned,
  • each vertex has integer coordinates,
  • each edge has integer length.

For a given integer $n$, define $P(n)$ as the number of distinct pythagorean polygons for which the perimeter is $≤ n$.

Pythagorean polygons should be considered distinct as long as none is a translation of another.

You are given that $P(4) = 1$, $P(30) = 3655$ and $P(60) = 891045$.
Find $P(120)$.

题意

我们定义满足以下条件的凸包是一个毕达哥拉斯多边形：

  • 至少包含三个点
  • 不存在三点共线
  • 所有点的横纵坐标都是整数
  • 所有边长都是整数

对于给定的 $n$，我们定义 $P(n)$ 是周长 $\leq n$ 的不同的毕达哥拉斯多边形的数量。

分析

显然可以记忆化搜索。

首先我们可以暴搜出所有可行的方向。可以发现可行的方向并不多。因为要求点和长度都是整数，意味着要么是平行x轴，要么是平行y轴，要么是一个两边长都是整数的直角三角形的斜边，而且斜边长是整数，例如 $(3,4,5)$ 。

然后为了保证是凸包，我们按照方向逆时针进行枚举，每次枚举出一个方向后，判断一下可以往这个方向延伸多少，然后check一下剩下的距离足够到原点嘛。稍微剪剪枝，就可以了。

代码

给大佬递上我奇丑无比的代码　(/ω＼)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include<bits/stdc++.h>

using namespace std;

const int max_coordinate = 85;

long long ans[max_coordinate << 1][max_coordinate << 1][130][140];

inline int gcd(int a, int b) {/*{{{*/
    if (a == 0) return b;
    return gcd(b % a, a);
}/*}}}*/
int check(int x, int y) {/*{{{*/
    if (gcd(x, y) != 1) return false;
    int buf = x * x + y * y;
    int sqrt_buf = sqrt(buf);
    if(sqrt_buf*sqrt_buf==buf) return sqrt_buf;
    return 0;
}/*}}}*/
inline int dis(int a, int b) {/*{{{*/
    return sqrt(a * a + b * b);
}/*}}}*/
struct dir {/*{{{*/
    int x, y, dis;

    dir() {};

    dir(int _x, int _y, int _dis) {
        x = _x, y = _y, dis = _dis;
    }

};/*}}}*/
dir all_dir[150];
int len_all_dir = 0;

bool cmp(dir a, dir b) {/*{{{*/
    return a.y * b.x < a.x * b.y;
}/*}}}*/
void init_all_dir() {/*{{{*/
    // domain 1
    for (int i = 0; i <= 85; i++)
        for (int j = 0; j <= 85; j++)
            if (check(i, j))
                all_dir[len_all_dir++] = dir(i, j, check(i, j));
    sort(all_dir, all_dir + len_all_dir, cmp);
    // domain 2
    int len = len_all_dir;
    for (int i = len - 2; i >= 0; i--) all_dir[len_all_dir++] = dir(-all_dir[i].x, all_dir[i].y, all_dir[i].dis);
    // domain 3, 4
    len = len_all_dir;
    for (int i = len - 2; i > 0; i--) all_dir[len_all_dir++] = dir(all_dir[i].x, -all_dir[i].y, all_dir[i].dis);
}/*}}}*/
long long gao(int x, int y, int len, int ind) {
    if (ans[x][y][len][ind] != -1) return ans[x][y][len][ind];
    if (x == max_coordinate && y == max_coordinate && len == 0) return ans[max_coordinate][max_coordinate][0][ind] = 1;
    ans[x][y][len][ind] = 0;
    for (int i = ind; i < len_all_dir; i++) {
        if (ind && all_dir[i].x == -all_dir[ind - 1].x && all_dir[i].y == -all_dir[ind - 1].y) continue;
        int upper = len / all_dir[i].dis;
        for (int j = 1; j <= upper; j++) {
            int new_x = x + all_dir[i].x * j;
            int new_y = y + all_dir[i].y * j;
            int new_len = len - all_dir[i].dis * j;
            int new_ind = i + 1;
            if (dis(new_x - max_coordinate, new_y - max_coordinate) > new_len) continue;
            ans[x][y][len][ind] += gao(new_x, new_y, new_len, new_ind);
        }
    }
    return ans[x][y][len][ind];
}

const int upper = 120;

int main() {
    init_all_dir();
    for (int i = 0; i < max_coordinate << 1; i++)
        for (int j = 0; j < max_coordinate << 1; j++)
            for (int k = 0; k < 130; k++)for (int l = 0; l < 140; l++) ans[i][j][k][l] = -1;
    long long ans = 0;
    for (int i = 4; i <= upper; i += 2) {
        long long buf = gao(max_coordinate, max_coordinate, i, 0);
        ans += buf;
        cout << i << ' ' << buf << ' ' << ans << endl;
    }
    cout << ans << endl;
    return 0;
}