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

· · 题解

题目传送门

题目分析

一道比较考察思维能力的题。

首先给出几个显而易见而十分重要的事实：

由上面两条事实可以发现，对于钝角三角形，根据第二条事实，平移某个顶点使其成为锐角三角形，然后根据第一条事实，可以把三角形平移使得某个顶点位于原点。因此可以将三角形的一个顶点锁定在 (0,0)，并且只需考虑锐角三角形的情况（之所以要锐角三角形，是防止有顶点的坐标为负）。下面用两张图解释上面说的：

如图，蓝色三角形就是我们变换后最终想要的三角形，而黄色三角形由于是钝角三角形，\angle KGJ>90^{\circ}，因此必然有一个点的坐标是负数，如图中的 J 点，不满足题意，因此我们要求是锐角三角形。

如图，这张图片展示了如何从钝角三角形变为锐角三角形。图中 OL\parallel MN，因此 S_{\triangle LMN}=S_{\triangle OMN} 且 \triangle OMN 是锐角三角形。这就是为什么我们只需要考虑锐角三角形的情况。

对于一般三角形，若顶点 A，B，C 的坐标分别为 (x_1,y_1)，(x_2,y_2)，(x_3,y_3)，我们有面积公式：

2S_{\triangle ABC}=\begin{vmatrix} x_1&y_1&1\\x_2&y_2&1\\x_3&y_3&1 \end{vmatrix}

由于我们把某一点（设为 A 点）移至了原点，因此 x_1=x_2=0，所以上述行列式的结果就为 x_2y_3-x_3y_2。所以我们有 A=x_2y_3-x_3y_2。因此我们要取适当的 x_2，x_3，y_2，y_3 满足每个 x 都位于 0 到 N 之间，每个 y 都位于 0 到 M 之间且满足 A=x_2y_3-x_3y_2。下面有一个好的构造。

设 k 为满足 (M-k)\times N\ge A 的最大正整数，则我们取 x_2=N，y_2=1，x_3=(M-k)\times N-A，y_3=M-k 即可满足要求。证明：

首先验证 A=x_2y_3-x_3y_2。我们有

x_2y_3-x_3y_2=N\times (M-k)-(M-k)\times N+A=A

然后验证 x 和 y 的范围。首先 x_2=N\le N，y_2=1\le M。假设 x_3>N，则 (M-k)\times N-A>N，变形得 (M-k-1)\times N>A，这与 k 的定义矛盾。因此 x_3\le N。而 y_3=M-k\le M。因此范围符合题意。

下面看什么时候无解，显然就是 k 取不到，也就是 MN<A 的时候。

以上就解决了这道题。

代码

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