可以算是一道数学题吧。如果知道皮克定理就好写多了。皮克定理说明了其面积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