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

D. Vasya and Triangle(几何)

程序员文章站 2022-03-02 10:21:36
...

题目链接

题意:给你三个数n,m,k。让你构造三个整数点,使得这三个点构成的三角形面积等于(n*m)/k;

题解:比赛的时候猜了一个结论就是2*(n*m)/k必须是整数,但是因为找不到证明的方法,然后写起来也比较复杂就放弃了。最后看了别人的题解发现还真是这样。

首先由解析几何,已知三个点坐标求 三角形面积
设A(x1,y1),B(x2,y2),C(x3,y3) 
由A-->B-->C-->A 按逆时针方向转。
即用三角形的三个顶点坐标求其面积的公式为: 
S=(1/2)*|(x1y2+x2y3+x3y1-x1y3-x2y1-x3y2)|                                                                                                                                     所以将三个整数点带进去,所得的面积乘2必定也是一个整数。

将一个点固定在原点,另外两个点分别固定在x轴正半轴,和y轴正半轴。

因为 2nm%k=0,则 2nm 必包含 k 所有的素因子,求得 u=gcd(2n,k)

若 u=1,显然 m 可以整除 k,令 x1=n,y2=2×m/k即可;

否则令 x1=2×n/u,y2=m×u/k即可。


 

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
	ll n,m,k;
	cin>>n>>m>>k;
	if(n*m*2%k!=0) return puts("NO"),0;
	ll u = __gcd(2*n,k);
	puts("YES");
	puts("0 0");
	if(u==1){
		cout<<n<<' '<<0<<endl;
		cout<<0<<' '<<2*m/k<<endl;
	}
	else {
		cout<<2*n/u<<' '<<0<<endl;
		cout<<0<<' '<<m*u/k<<endl;
	}
 } 

 

相关标签: 几何