专栏文章

题解：P13467 [GCJ 2008 #2] Triangle Areas

jjsisonx
P13467题解参与者 3已保存评论 2

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
2 条
当前快照
1 份
快照标识符
@miomwa65
此快照首次捕获于
2025/12/02 21:48
3 个月前
此快照最后确认于
2025/12/02 21:48
3 个月前
查看原文
题目传送门

题目分析

一道比较考察思维能力的题。
首先给出几个显而易见而十分重要的事实：
  • 三角形平移后面积不变。
  • 三角形某个顶点沿与其对边平行的方向平移，三角形面积不变（等底等高）。
由上面两条事实可以发现，对于钝角三角形，根据第二条事实，平移某个顶点使其成为锐角三角形，然后根据第一条事实，可以把三角形平移使得某个顶点位于原点。因此可以将三角形的一个顶点锁定在 (0,0)(0,0)，并且只需考虑锐角三角形的情况（之所以要锐角三角形，是防止有顶点的坐标为负）。下面用两张图解释上面说的：
如图，蓝色三角形就是我们变换后最终想要的三角形，而黄色三角形由于是钝角三角形，∠KGJ>90∘\angle KGJ>90^{\circ}，因此必然有一个点的坐标是负数，如图中的 JJ 点，不满足题意，因此我们要求是锐角三角形。
如图，这张图片展示了如何从钝角三角形变为锐角三角形。图中 OL∥MNOL\parallel MN，因此 S△LMN=S△OMNS_{\triangle LMN}=S_{\triangle OMN} 且 △OMN\triangle OMN 是锐角三角形。这就是为什么我们只需要考虑锐角三角形的情况。
对于一般三角形，若顶点 AA，BB，CC 的坐标分别为 (x1,y1)(x_1,y_1)，(x2,y2)(x_2,y_2)，(x3,y3)(x_3,y_3)，我们有面积公式：
2S△ABC=∣x1y11x2y21x3y31∣2S_{\triangle ABC}=\begin{vmatrix} x_1&y_1&1\\x_2&y_2&1\\x_3&y_3&1 \end{vmatrix}
由于我们把某一点（设为 AA 点）移至了原点，因此 x1=x2=0x_1=x_2=0，所以上述行列式的结果就为 x2y3−x3y2x_2y_3-x_3y_2。所以我们有 A=x2y3−x3y2A=x_2y_3-x_3y_2。因此我们要取适当的 x2x_2，x3x_3，y2y_2，y3y_3 满足每个 xx 都位于 00 到 NN 之间，每个 yy 都位于 00 到 MM 之间且满足 A=x2y3−x3y2A=x_2y_3-x_3y_2。下面有一个好的构造。
设 kk 为满足 (M−k)×N≥A(M-k)\times N\ge A 的最大正整数，则我们取 x2=Nx_2=N，y2=1y_2=1，x3=(M−k)×N−Ax_3=(M-k)\times N-A，y3=M−ky_3=M-k 即可满足要求。证明：
首先验证 A=x2y3−x3y2A=x_2y_3-x_3y_2。我们有
x2y3−x3y2=N×(M−k)−(M−k)×N+A=Ax_2y_3-x_3y_2=N\times (M-k)-(M-k)\times N+A=A
然后验证 xx 和 yy 的范围。首先 x2=N≤Nx_2=N\le N，y2=1≤My_2=1\le M。假设 x3>Nx_3>N，则 (M−k)×N−A>N(M-k)\times N-A>N，变形得 (M−k−1)×N>A(M-k-1)\times N>A，这与 kk 的定义矛盾。因此 x3≤Nx_3\le N。而 y3=M−k≤My_3=M-k\le M。因此范围符合题意。
下面看什么时候无解，显然就是 kk 取不到，也就是 MN<AMN<A 的时候。
以上就解决了这道题。

代码

CPP
#include<bits/stdc++.h>
using namespace std;
int main(){
	int t;
	cin>>t;
	for(int o=1;o<=t;o++){
		cout<<"Case #"<<o<<": ";
		long long n,m,a;
		cin>>n>>m>>a;
		if(a>m*n){
			cout<<"IMPOSSIBLE"<<endl;
			continue;
		}
		cout<<0<<' '<<0<<' ';
		long long m0=0;
		for(long long i=0;i<=m;i++){
			if(n*(m-i)>=a&&n*(m-i-1)<a){
				m0=i;
				break;
			}
		}
		cout<<n<<' '<<1<<' '<<(m-m0)*n-a<<' '<<m-m0<<endl;
	}
	return 0;
}

评论

共 2 条评论，欢迎与作者交流。

正在加载评论...