Beyond the Void
BYVoid
USACO 3.4.3 Electric Fence 電網
本文正體字版由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

相關日誌