本文正體字版由OpenCC轉換
可以算是一道數學題吧。如果知道皮克定理就好寫多了。皮克定理說明了其面積S和內部格點數目a、邊上格點數目b的關係：S = a + b/2 - 1。 根據三角形面積公式求出S。如果知道了b，那麼三角形內部格點數目a也就求出來了。 可以證明，一條直線((0,0),(n,m))上的格點數等於n與m的最大公約數+1。 即b=gcd(n,m)+1. gcd(n,m)爲n與m的最大公約數。 代入皮克公式，即可求出a的值.
USER: CmYkRgB CmYkRgB [cmykrgb1] TASK: fence9 LANG: C++
Compiling… Compile: OK
Executing… Test 1: TEST OK [0.011 secs, 2840 KB] Test 2: TEST OK [0.000 secs, 2844 KB] Test 3: TEST OK [0.011 secs, 2844 KB] Test 4: TEST OK [0.000 secs, 2844 KB] Test 5: TEST OK [0.011 secs, 2844 KB] Test 6: TEST OK [0.000 secs, 2840 KB] Test 7: TEST OK [0.011 secs, 2840 KB] Test 8: TEST OK [0.000 secs, 2840 KB] Test 9: TEST OK [0.000 secs, 2840 KB] Test 10: TEST OK [0.000 secs, 2840 KB] Test 11: TEST OK [0.022 secs, 2840 KB] Test 12: TEST OK [0.000 secs, 2840 KB]
汗，USACO居然有重名的題.
/*
ID: cmykrgb1
PROG: fence9
LANG: C++
*/
#include <iostream>
#include <fstream>
using namespace std;
ifstream fi("fence9.in");
ofstream fo("fence9.out");
long n,m,p,ans;
void init()
{
fi >> n >> m >> p;
}
long gcd(long x,long y)
{
int tmp;
while (y>0)
{
tmp=y;
y=x % y;
x=tmp;
}
return x;
}
void compute()
{
double S,b;
long w1,w2;
S=p*m/2.0;
w1=gcd(n,m);
w2=gcd(m,abs(p-n));
b=p+w1+w2;
ans=S-b/2.0+1;
}
void print()
{
fo << ans << endl;
fi.close();
fo.close();
}
int main()
{
init();
compute();
print();
return 0;
}
上次修改時間 2017-02-03