#P3086. Coci2009 dvapravca

    ID: 2241 传统题 1000ms 512MiB 尝试: 71 已通过: 26 难度: 9 上传者: 标签>CF2600提高+/省选-投影扫描线事件排序叉积普通线段树普通并查集同时事件分阶段处理时间戳避免清空数组

Coci2009 dvapravca

题目描述

给定平面上的 nn 个点,其中有一些是红的,其他是蓝的。现在让你找两条平行的直线,使得在保证不存在一个蓝色的点被夹在两条平行线之间,不经过任何一个点,不管是蓝色点还是红色点的前提下,被夹在平行线之间的红色点个数最多是多少?

输入格式

第 11 行一个整数 nn。

第 22 到 n+1n+1 行,每行是一个点的坐标以及它的颜色。坐标用 22 个绝对值 <109<10^9 的整数表示颜色用 R 或 B 表示。

输出格式

第 11 行仅一个整数,被夹在平行线之间的红色点个数的最大值。

4
0 0 R
0 1 B
1 1 R
1 0 B
2

数据规模与约定

对于 100%100\% 的数据,1≤n≤1031\le n\le 10^3。