题解 P7042 【「MCOI-03」正方】

Thomas_Cat · 2020-10-31 18:27:09 · 题解

今日月赛第一题题解：

我们先来观察题目，根据题目中给的这个正方形（如图）我们可以得出结论：

• 这个图必须是一个正方形

• 这个图必须由四部分的比例 a : b : c : d 组成，否则无效

• 这个图的底是相等的，因为正方形四边边长相等不妨把底边 AB ,BC , CD, AD 设为 l

  于是我们得出公式：S \triangle AED : S \triangle AEB : S \triangle CEB : S \triangle DEC = a \times l : b \times l : c \times l : d \times l 。

• 根据上图公式，直接判断即可

接下来来讲一下判断方法和内容：

就拿样例来说：

• a : b : c : d = 1 : 3 : 3 : 1

我们发现，正方形的边长应该是 (a+b),(c+d),(a+c),(b+d) = 1 + 3 = 4 。

我们就画出一个 4 \times 4 的正方形：

紧接着，我们在上面 作图 如上图给出的图片一样，看看能找到多少个：

于是乎我们发现四种情况（下图四个图形为四种情况，并不是四个正方形）：

• a : b : c : d = 2 : 4 : 7 : 8

  我们发现，我们不可能组成一个正方形，因为：

  • a+b \ne c+d
  • a+c \ne b+d
  • a+d \ne b+c
• a : b : c : d = 2 : 3 : 1 : 4

  我们发现，正方形的边长应该是 (a+b),(c+d) = (2 + 3) , (1 + 4)=5

  我们画出 5 \times 5 的正方形，寻找规律：

  于是乎我们发现了八种情况。

于是我们发现：

• 当 a = b / a=c/a=d/b=c/b=d/c=d 时，答案为 4 。
• 当 a = b = c = d 时，答案为 1 。
• 当 a \ne b \ne c \ne d 时，答案为 8 。
• 当 a,b,c,d 不构成四边形也就是：
  • a+b \ne c+d
  • a+c \ne b+d
  • a+d \ne b+c

    时，答案为 0 。

于是我们得出代码：

#include<iostream>
using namespace std;
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        unsigned long long a,b,c,d;
        cin>>a>>b>>c>>d;
        if(a==b&&a==c&&a==d&&b==c&&b==d&&c==d) cout<<1<<endl;
        else if(a+b==c+d||a+c==b+d||a+d==b+c){
            if(a==b||a==c||a==d||b==c||b==d||c==d) cout<<4<<endl;
            else if(a!=b||a!=c||a!=d||b!=c||b!=d||c!=d) cout<<8<<endl;
        }
        else cout<<0<<endl;
    }
    return 0;
}

Ps : 数据范围因为是 1 \le a,b,c,d \le 10^{18}，所以需要使用 ull