唯寻国际教育旗下唯一官方网站
课程咨询热线 400-825-6055
为什么选择唯寻

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

09-16

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

USACO比赛难度高吗?用一道真题解析告诉你内容图片_1


USACO比赛真题:三角形牧场

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

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

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

USACO比赛难度高吗?用一道真题解析告诉你内容图片_2

输入(triangles.in)

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


输出(triangles.out)

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


样例:

triangles.intriangles.out样例解释
4
0  0
0  1
1  0
1  2
3

位于点 (0,0)、(1,0) 和 (1,2) 

的木桩组成了一个面积为 1的三角形。

所以,答案为 2x1=2。
只有一个其他的三角形,面积为 0.5。

解题思路

思路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藤校竞赛备考班,让国内最有经验之一的竞赛导师团队带你全面提升比赛实力,花样启发竞赛思维。

USACO比赛难度高吗?用一道真题解析告诉你内容图片_3

USACO比赛难度高吗?用一道真题解析告诉你内容图片_4

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

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

热门标签:
为什么选择唯寻

预约试听课

您的身份是:
*
*
相关文章推荐
唯寻名师推荐
换一换

Elaine Xu

牛津大学数学与统计专业学士

牛津大学数学与统计专业学士

Alevel成绩:A*A*A*A

毕业后投身教育事业,5年留学行业学生背景提升、项目产品开发经验

擅于挖掘学生特质,结合其特长开发学生潜能,打造升学背景

指导近百名高中生成功录取英国牛剑、G5、美国卡内基梅隆、康奈尔、UCB、纽大、卡尔顿学院等世界名校