USACO比赛难度高吗？用一道真题解析告诉你

一直有对编程感兴趣的同学好奇USACO比赛的难度，我们今天直接通过分析1道2020年1月赛的真题来让大家感受USACO比赛的真实难度。

USACO计算机竞赛是什么？

USACO是一项针对全世界所有的国际学校信息学竞赛选手的一项竞赛。这项赛事不仅可以培养学员的算法和编程思维，好的竞赛成绩还能给学员大学申请加分。

USACO计算机竞赛时间：

每年的12月、1月、2月和3月都分别有USACO比赛开放日，在比赛窗口开放的三天内，选手可以选择在任意时间登陆USACO账号开始比赛。

每场比赛4—5个小时，比赛从打开试题后开始计时，可以使用C++，Java，Python，Pascal和C中的任意一种语言进行做题，在时间结束前通过网络将写好的程序提交即可。

USACO比赛真题：三角形牧场

题目描述：Farmer John 想要给他的奶牛们建造一个三角形牧场。

有 N（3≤N≤100）个栅栏柱子分别位于农场的二维平面上不同的点 (X1,Y1)…(XN,YN)。他可以选择其中三个点组成三角形牧场，只要三角形有一条边与 x 轴平行，且有另一条边与 y 轴平行。

Farmer John 可以围成的牧场的最大面积是多少？助力存在至少一个合法的三角形牧场。

输入(triangles.in)：

第一行包含整数 N。以下 N 行每行包含两个整数 Xi 和 Yi，均在范围 −104…104 之内，描述一个栅栏柱子的位置。

输出(triangles.out)：

由于面积不一定为整数，输出栅栏柱子可以围成的合法三角形的最大面积的两倍。

样例：

解题思路

思路1：暴力搜索

考虑到输入的点至多是100，任取3点组成1个三角形，总共有C(100, 3) = 100! / (3! * 97!) = 323,400个可能的三角形。故，可以通过3重循环枚举每个可能的三角形。

那么对于给定的3个点A,B,C 如何判断它是符合条件的三角形呢？三角形有一条边与 x 轴平行，且有另一条边与 y 轴平行。不妨假设A为这个三角的直角顶点，那么，A,B,C应满足Ax == Bx and Ay == Cy 或 Ax == Cx and Ay == By。故，符合条件的三角形需满足以下情况之一即可：

(Ax == Bx and Ay == Cy) or (Ax == Cx and Ay == By)

(Bx == Ax and By == Cy) or (Bx == Cx and Ay == By)

(Cx == Bx and Ay == Cy) or (Ax == Cx and Ay == Cy)

对于题目要求的最大面积的2倍，我们可以用变量answer保存，初始化为0。一旦找到一个合法的三角形，计算其面积的2倍area，则answer = max(answer, area)。

面积如何计算，就留给各位读者啦。

伪代码：

for i in range(N):

    for j in range(i+1, N):

        for k in range(j+1, N):

           A = P[i]; B=P[j]; C=P[k]

             if Ax == Bx and Ay == Cy:

              #计算面积 area

          answer = max(answer, area)

     elif Ax == Bx and Ay == Cy:

       ......

思路2：枚举直角三角形

前面的暴力搜索把所有可能的三角形都枚举了一遍，再判断三角形是否满足要求。那么是不是可以直接枚举合法的三角形呢？

考虑到三角形有一条边与 x 轴平行，且有另一条边与 y 轴平行，我们可以先把所有的点按x分类（x值相同的所有点归在一起），也按y分类（y值相同的所有点归在一起）。

对于任意一点（Xi，Yi）可以找到平行于y轴的另一个顶点（Xr，Yr），Yi ≠ Yr, Xi = Xr；和平行于x轴的另一个顶点（Xk，Yk）, Xi ≠ Xk, Yi = Yk。该三角形的面积的2倍为abs(Yi - Yr) * abs(Xi - Xk)，最大值即为max{abs(Yi - Yr), Yi ≠ Yr, Xi = Xr} * max{abs(Xi - Xk), Xi ≠ Xk, Yi = Yk}

上述的分类工作，可以通过dict完成。这里推荐使用defaultdict，可以设置default值。

伪代码：

from collections import defaultdict

points_by_x = defaultdict(list)

points_by_y = defaultdict(list)

points = []

for i in range(N):

   #读取输入点(x, y)

   points.append(x, y)

   points_by_x[x].append(y)

   points_by_y[y].append(x)

for point in points:

   #获得点(x, y)

   side1 = 0; side2 = 0

for other_y in points_by_x[x]:

   if y != other_y:

      # 计算side1

for other_x in points_by_y[y]:

   if x != other_x:

     # 计算side2

#计算面积 area

answer = max(answer, area)

以上2种USACO比赛真题的解法哪种效率更高，就留给大家自己去思考啦。在感受了USACO比赛的真实难度后，如果觉得孤军奋战有点辛苦，不如来预约试听橡沐的G5藤校竞赛复习班，让国内最有经验之一的竞赛导师团队带你全面提升比赛实力，花样启发竞赛思维。

有备而来的你一定比对竞赛一无所知的对手更有机会拿奖。快加入橡沐，打通竞赛这个本科申请背景提升的最佳通道吧。

更多国际竞赛实用信息点击USAMO数学竞赛难度、BPHO竞赛含金量阅读。