Description
给定平面上的 N 个点, 其中有一些是红的, 其他是蓝的.现在让你找两条平行的直线, 使得在保证
不存在一个蓝色的点 被夹在两条平行线之间,不经过任何一个点, 不管是蓝色点还是红色点
的前提下,
被夹在平行线之间的红色点个数最多
Input
第1行: 一个整数 N (1 <= N <= 1000)
第2..N+1行: 每行是一个点的坐标以及它的颜色.
坐标用2个 绝对值<10^9
的整数表示
颜色用 'R' 或 'B' 表示
Output
第1行: 仅一个整数, 被夹在平行线之间的红色点个数的最大值
Sample Input
4
0 0 R
0 1 B
1 1 R
1 0
B
0 0 R
0 1 B
1 1 R
1 0
B
Sample Output
2
先考虑一下如果这两条直线必须与x轴垂直怎么做，我们先可以将所有点按x为第一关键字，y为第二关键字排序，在这个排好序的序列中找到最长的一段红色就是答案了（用线段树维护）
然后我们把坐标系旋转，如果y轴扫过了两点连成的直线，则这两个点的排名就会交换，旋转一周交换的点对为O（N2)个,所以可以用一个线段树来维护区间最长红点数，支持单点修改和查询，复杂度O（N2logN）。
code：
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#define maxn 1005
using namespace std;
int n,m,a,b,ans,pos[maxn];
char s[];
inline int min(const int &a,const int &b){
int diff=b-a;
return a+(diff&(diff>>));
}
inline int max(const int &a,const int &b){
int diff=b-a;
return b-(diff&(diff>>));
}
struct Point{
int x,y,col;
}point[maxn];
inline bool cmp1(Point a,Point b){
if (a.x!=b.x) return a.x<b.x;
return a.y<b.y;
}
struct Line{
int a,b,x,y;
}line[maxn*maxn];
inline bool cmp2(const Line &a,const Line &b){return 1LL*a.x*b.y<1LL*a.y*b.x;}
inline bool cmp(const Line &a,const Line &b){return 1LL*a.x*b.y==1LL*a.y*b.x;}
struct Seg{
#define ls k<<1
#define rs (k<<1)+1
int val[maxn<<],lmax[maxn<<],rmax[maxn<<],col[maxn<<];
inline void update(int k){
col[k]=col[ls]|col[rs];
lmax[k]=(col[ls])?lmax[ls]:lmax[ls]+lmax[rs];
rmax[k]=(col[rs])?rmax[rs]:rmax[ls]+rmax[rs];
val[k]=max(rmax[ls]+lmax[rs],max(val[ls],val[rs]));
}
inline void modify(int k,int l,int r,int x,int c){
if (l==r){val[k]=lmax[k]=rmax[k]=c^,col[k]=c;return;}
int m=(l+r)>>;
if (x<=m) modify(ls,l,m,x,c); else modify(rs,m+,r,x,c);
update(k);
}
}T;
int main(){
scanf("%d",&n);
for (int i=;i<=n;i++){
scanf("%d%d%s",&point[i].x,&point[i].y,s);
point[i].col=(s[]=='B'),pos[i]=i;
}
sort(point+,point+n+,cmp1);
for (int i=;i<=n;i++) for (int j=i+;j<=n;j++)
line[++m]=(Line){i,j,point[j].x-point[i].x,point[j].y-point[i].y};
sort(line+,line+m+,cmp2);
for (int i=;i<=n;i++) T.modify(,,n,i,point[i].col);
ans=T.val[];
for (int i=,j=;i<=m;i=j){
for (;j<=m&&cmp(line[i],line[j]);j++){
a=line[j].a,b=line[j].b;
T.modify(,,n,pos[b],point[a].col);
T.modify(,,n,pos[a],point[b].col);
swap(pos[a],pos[b]);
ans=max(ans,T.val[]);
}
}
printf("%d\n",ans);
return ;
}