Codeforces Round #512 (Div. 2) - D. Vasya and Triangle (皮克公式)
程序员文章站
2022-05-09 22:00:21
...
http://codeforces.com/contest/1058/problem/D
题意:
在x [0,n]. y[0,m]的坐标系中,找到一个格点三角形(三角形的顶点全在格点上),他的面积是n*m/k.
POINT:
皮克定理是指一个计算点阵中顶点在格点上的多边形面积公式,该公式可以表示为2S=2a+b-2,其中a表示多边形内部的点数,b表示多边形边界上的点数,S表示多边形的面积。
所以2*m*n/k一定要是一个整数,才能有答案。
#include <iostream>
#include <stdio.h>
using namespace std;
#define LL long long
const int mod = 1e9+7;
LL gcd(LL a,LL b)
{
return b==0?a:gcd(b,a%b);
}
int main()
{
LL n,m,k;
cin>>n>>m>>k;
if(2*n*m%k!=0) cout<<"NO"<<endl;
else{
LL g=gcd(k,2*n);
if(g==1) m=2*m/k;
else{
n=2*n/g;
m=m*g/k;
}
printf("YES\n0 0\n%lld 0\n0 %lld\n",n,m);
}
}