Description
给定平面上的 N 个点, 其中有一些是红的, 其他是蓝的.现在让你找两条平行的直线, 使得在保证
不存在一个蓝色的点 被夹在两条平行线之间,不经过任何一个点, 不管是蓝色点还是红色点
的前提下, 被夹在平行线之间的红色点个数最多
Input
第1行: 一个整数 N (1 <= N <= 1000)
第2..N+1行: 每行是一个点的坐标以及它的颜色.
坐标用2个 绝对值<10^9 的整数表示
颜色用 'R' 或 'B' 表示
Output
第1行: 仅一个整数, 被夹在平行线之间的红色点个数的最大值
令一条直线l垂直于所选平行直线，将点投影到直线上，考虑点的投影之间相对位置构成的序列，则问题转化为求序列的最长红色子串
直线旋转180度，则枚举了所有可能的倾斜角，而任意两点投影的相对位置只会发生一次变化，序列变化了O(n^2)次，因此可以用线段树维护这个序列同时维护最长红色子串
只能在序列上的投影点不发生重合时更新答案
#include<cstdio>
#include<algorithm>
typedef long long i64;
int n,ep=,ans=;
struct pos{
int x,y;
};
pos operator-(pos a,pos b){
return (pos){a.x-b.x,a.y-b.y};
}
i64 operator*(pos a,pos b){
return i64(a.x)*b.y-i64(a.y)*b.x;
}
struct point{
pos a;
int col;
bool operator<(const point&w)const{return a.y!=w.a.y?a.y<w.a.y:a.x<w.a.x;}
}ps[];
struct ev{
pos x;
int a,b;
bool operator<(const ev&w)const{return x*w.x<;}
}es[*];
char str[];
int ls[],rs[],ms[],ws[],sz[];
int max(int a,int b){return a>b?a:b;}
inline void up(int w,int l,int r){
ms[w]=max(ms[l],max(ms[r],rs[l]+ls[r]));
ls[w]=ls[l];
if(ls[l]==sz[l])ls[w]+=ls[r];
rs[w]=rs[r];
if(rs[r]==sz[r])rs[w]+=rs[l];
}
void set(int w,int v){
for(w+=,ls[w]=rs[w]=ms[w]=v,w>>=;w;w>>=)up(w,w<<,w<<^);
}
int main(){
scanf("%d",&n);
for(int i=;i<=n;++i){
scanf("%d%d%s",&ps[i].a.x,&ps[i].a.y,str);
ps[i].col=str[]=='R';
}
std::sort(ps+,ps+n+);
for(int i=;i<=n;++i){
for(int j=;j<=n;++j){
pos w=ps[j].a-ps[i].a;
if(w.y>||w.y==&&w.x>)es[ep++]=(ev){w,i,j};
}
}
for(int i=;i<=n;++i){
ws[i]=i;
sz[i+]=;
if(ps[i].col)ls[i+]=rs[i+]=ms[i+]=;
}
for(int i=;i;--i)sz[i]=sz[i<<]+sz[i<<^],up(i,i<<,i<<^);
ans=ms[];
std::sort(es,es+ep);
for(int i=,j=;i<ep;){
for(;j<ep&&es[i].x*es[j].x==;++j);
for(;i<j;++i){
int a=es[i].a,b=es[i].b;
std::swap(ws[a],ws[b]);
if(ps[a].col!=ps[b].col){
set(ws[a],ps[a].col);
set(ws[b],ps[b].col);
}
}
ans=max(ans,ms[]);
}
printf("%d",ans);
return ;
}