usaco training 3.4.3 fence9 题解

In this problem, `lattice points‘ in the plane are points with integer coordinates.

In order to contain his cows, Farmer John constructs a triangular electric fence by stringing a "hot" wire from the origin (0,0) to a lattice point [n,m] (0<=;n<32,000, 0<m<32,000), then to a lattice point on the positive x axis [p,0] (0<p<32,000), and then back to the origin (0,0).

A cow can be placed at each lattice point within the fence without touching the fence (very thin cows). Cows can not be placed on lattice points that the fence touches. How many cows can a given fence hold?

PROGRAM NAME: fence9

INPUT FORMAT

The single input line contains three space-separated integers that denote n, m, and p.

OUTPUT FORMAT

A single line with a single integer that represents the number of cows the specified fence can hold.

       前言：咳咳，正当我向大视野、PKU等众多题库征战的时候，我猛然发现最最经典的USACO原题我竟然还没有刷完！！！于是最近我要把这个刷到5、6版，并且会陆续写一些题解。（水题就不解释了）

预备知识：皮克定理

a=39,b=14,s=45

对于这道题目，肯定很多人开始都束手无策，但是看到这个公式后就豁然开朗。我们先求出这个三角形的面积和位于三角形边上的点（GCD来求），在反向套用皮克定理，求出其内部的点。

代码：

{
ID:juan1973
LANG:PASCAL
PROG:fence9
}
var
  n,m,p,on_the_line,left_up,right_up,ans:longint;
function gcd(a,b:longint):longint;
begin
  if a mod b=0 then exit(b);
  exit(gcd(b,a mod b));
end;
begin
  assign(input,‘fence9.in‘);
  assign(output,‘fence9.out‘);
  reset(input);
  rewrite(output);

  readln(n,m,p);
  if n=0 then left_up:=m else left_up:=gcd(n,m);
  if abs(n-p)>0 then right_up:=gcd(abs(n-p),m) else right_up:=m;
  on_the_line:=left_up+right_up+p;
  ans:=(p*m-on_the_line) div 2+1;
  writeln(ans);

  close(input);
  close(output);
end.

usaco training 3.4.3 fence9 题解

原文：http://blog.csdn.net/jiangshibiao/article/details/19910987