Codeforces 1030D 【构造】

题目大意：给你n，m，k，让你在一个n*m的点阵里构造出一个面积为\(\frac{n*m}{k}\)的三角形

思路

首先要有一个结论是整点三角形的面积分母最多为2，然后就可以判断不存在的情况了

接下来就直接进行构造就可以了

#include<bits/stdc++.h>

using namespace std;

#define LL long long

#define IL inline

#define fu(a,b,c) for(LL a=b;a<=c;++a)

#define fd(a,b,c) for(LL a=b;a>=c;--a)

#define FLIE ""

IL LL read(){

  LL ans=0,w=1;char c=getchar();

  while(!isdigit(c)&&c!='-')c=getchar();

  if(c=='-')w=-1,c=getchar();

  while(isdigit(c))ans=(ans<<1)+(ans<<3)+c-'0',c=getchar();

  return ans*w;

}

LL n,m,k,g,ttmp,f=-1;

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

int main(){

	n=read(),m=read(),k=read();

	LL g1=gcd(n,k);

	n/=g1,k/=g1;if(g1!=1)f=1,ttmp=g1;

	LL g2=gcd(m,k);

  m/=g2,k/=g2;if(g2!=1)f=2,ttmp=g2;

	if(k>2)puts("NO");

  else{puts("YES");

	  if(k==1){

		  if(f==1)n*=2;

		  else m*=2;

	  }

	  printf("0 0\n%I64d 0\n0 %I64d",n,m);

  }

  return 0;

}

巴特西

Codeforces 1030D 【构造】

思路

最新文章

热门文章