USACO 3.4 Electric Fence

时间：2024-08-11 23:06:44

Electric Fence
Don Piele

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.

SAMPLE INPUT (file fence9.in)

7 5 10

OUTPUT FORMAT

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

SAMPLE OUTPUT (file fence9.out)

20
——————————————————————————————————
皮克定理，在格点多边形S=a+b/2-1 其中a是多边形内部的点数，b是多边形边上的点数
先mark，考完期末之后回来看证明 2017.1.2
 /*

 ID: ivorysi

 PROG: fence9

 LANG: C++

 */

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #include <queue>

 #include <set>

 #include <vector>

 #include <string.h>

 #define siji(i,x,y) for(int i=(x);i<=(y);++i)

 #define gongzi(j,x,y) for(int j=(x);j>=(y);--j)

 #define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)

 #define sigongzi(j,x,y) for(int j=(x);j>(y);--j)

 #define inf 0x3f3f3f3f

 #define MAXN 400005

 #define ivorysi

 #define mo 97797977

 #define ha 974711

 #define ba 47

 #define fi first

 #define se second

 #define pii pair<int,int>

 using namespace std;

 typedef long long ll;

 int n,m,p;

 int s,k;

 int gcd(int a,int b) {return b== ? a : gcd(b,a%b);}

 void solve() {

     scanf("%d%d%d",&n,&m,&p);

     s=p*m;

     k=k+gcd(m,n)-;

     k=k+gcd(abs(n-p),m)-;

     k=k++p;

     int ans=(s-k+)/;

     printf("%d\n",ans);

 }

 int main(int argc, char const *argv[])

 {

 #ifdef ivorysi

     freopen("fence9.in","r",stdin);

     freopen("fence9.out","w",stdout);

 #else

     freopen("f1.in","r",stdin);

 #endif

     solve();

 }
 

相关文章