欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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);
	}



}