#PU514. USACO 2015 January Contest, Gold — Problem 1. Cow Rectangles

    ID: 1443 传统题 2000ms 256MiB 尝试: 0 已通过: 0 难度: 提高+/省选- 上传者: 标签>USACO赛事:jan15来源:usaco.orgscoring:equal_test_cases枚举

USACO 2015 January Contest, Gold — Problem 1. Cow Rectangles

USACO 2015 January Contest, Gold — Problem 1. Cow Rectangles

题目描述

Problem 1: Cow Rectangles [Nick Wu, 2015]

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.

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

5
1 1 H
2 2 H
3 3 G
4 4 H
6 6 H
2
1