P3117 [USACO15JAN]牛的矩形Cow Rectangles

    • 30通过
    • 103提交
  • 题目提供者 FarmerJohn2
  • 评测方式 云端评测
  • 标签 分治 单调队列 队列 USACO 2015 高性能
  • 难度 省选/NOI-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

    The locations of Farmer John's N cows (1 <= N <= 500) are described by distinct points in the 2D plane. The cows belong to two different breeds: Holsteins and Guernseys. Farmer John wants to build a rectangular fence with sides parallel to the coordinate axes enclosing only Holsteins, with no Guernseys (a cow counts as enclosed even if it is on the boundary of the fence). Among all such fences, Farmer John wants to build a fence enclosing the maximum number of Holsteins. And among all these fences, Farmer John wants to build a fence of minimum possible area. Please determine this area. A fence of zero width or height is allowable.

    约翰的N(1 <= N <= 500)头奶牛的位置由坐标平面上的点来描述。这些奶牛分为两种:Holsteins 和 Guernseys。约翰想要修建一个矩形的围栏,围栏的边平行于x轴或者y轴,并且要求围栏中只有Holsteins类型的奶牛(一头奶牛在围栏的边边上也算在围栏以内)。

    约翰想要使围栏围住进可能多的Holsteins奶牛,在此基础上,约翰希望围栏构成的矩形的面积尽可能小,请你计算出这个最小面积。

    注意:围栏的长或宽为0的情况是允许的。

    输入输出格式

    输入格式:

    INPUT: (file cowrect.in)

    The first line of input contains N. Each of the next N lines

    describes a cow, and contains two integers and a character. The integers indicate a point (x,y) (0 <= x, y <= 1000) at which the cow is located. The character is H or G, indicating the cow's breed. No two cows are located at the same point, and there is always at least one Holstein.

    输出格式:

    OUTPUT: (file cowrect.out)

    Print two integers. The first line should contain the maximum number

    of Holsteins that can be enclosed by a fence containing no Guernseys,

    and second line should contain the minimum area enclosed by such a

    fence.

    输入输出样例

    输入样例#1: 复制
    5 
    1 1 H 
    2 2 H 
    3 3 G 
    4 4 H 
    6 6 H 
    
    输出样例#1: 复制
    2 
    1 
    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。