Skip to content

Instantly share code, notes, and snippets.

@vwrs
Last active February 23, 2016 15:15
Show Gist options
  • Save vwrs/3b8364ba6a3dbe2bd7ee to your computer and use it in GitHub Desktop.
Save vwrs/3b8364ba6a3dbe2bd7ee to your computer and use it in GitHub Desktop.
Problem 504
#include <tgmath.h>
#include <stdio.h>
#include <stdlib.h>
// 20s
// Euclidean Algorithm
int gcd(int x, int y){
if(y < 1) exit(0); // error
int z;
if(x < y){
z = x;
x = y;
y = z;
}
if(x % y == 0) return y;
return gcd(y, x % y);
}
int is_square(int a, int b, int c, int d){
int lp_contains = ((a+c)*(b+d)/2) - (gcd(a,b) + gcd(b,c) + gcd(c,d) + gcd(d,a)) / 2 + 1;
return pow((int)sqrt(lp_contains), 2) == lp_contains;
}
int main(){
int m = 100;
// printf("input m: "); scanf("%d", &m);
int lp_square = 0; // answer
for(int a = 1; a <= m; a++){
for(int b = 1; b <= m; b++){
for(int c = 1; c <= m; c++){
for(int d = 1; d <= m; d++){
if(is_square(a, b, c, d)) lp_square++;
}
}
}
}
printf("answer: %d\n", lp_square);
}
# Problem 504
# 1[m]28[s]
# def get_area(a, b, c, d)
# return (a+c) * (b+d) / 2
# end
# def get_LP_side(a, b, c, d)
# return a.gcd(b) + b.gcd(c) + c.gcd(d) + d.gcd(a)
# end
# Pick's theorem
# def get_LP(area, lp_side)
# return area - lp_side/2 + 1
# end
def is_square(a, b, c, d)
lp_contains = ((a+c)*(b+d)/2) - (a.gcd(b) + b.gcd(c) + c.gcd(d) + d.gcd(a)) / 2 + 1
return Math.sqrt(lp_contains).to_i ** 2 == lp_contains
end
m = 100
# print 'input m: '
# m = gets.to_i;
lp_square = 0 # answer
1.upto(m){|a| 1.upto(m){|b| 1.upto(m){|c| 1.upto(m){|d| lp_square += 1 if is_square(a,b,c,d) } } } }
puts "#{lp_square} quadrilaterals strictly contain a square number of lattice points in m = #{m}"
@vwrs
Copy link
Author

vwrs commented Feb 21, 2016

504

文法を学ぶことも兼ねてRubyで最初に作成した。アルゴリズムは変えずにCで実装したところ,実行時間はおよそ 2/9 になった。

@vwrs
Copy link
Author

vwrs commented Feb 21, 2016

四角形ABCDに含まれる格子点を求める際ピックの定理を用いた。
完全に四角形の内部に含まれる格子点を求めるには,面積とABCDの辺上の格子点の数を求めれば良い。
辺上の格子点の数を求めるのに,最大公約数を用いた。

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment