我真的弱,正解都不会还打了个错的暴力
考虑平行线与x轴平行,那么可以按照y为第一关键字升序,x为第二关键字升序排序,然后合法的一段红点就是连续的一段,答案也就是最大的连续红色段
推广到一般情况,我们可以把所有点绕原点旋转,每次转着都会有两个点排序后的相对位置交换,可以用线段树维护答案,每次单点修改,取出全局最大连续段更新答案
#include<bits/stdc++.h>
#define LL long long
#define db double
#define il inline
#define re register
using namespace std;
const int N=1000+10;
const db pi=acos(-1),eps=1e-10;
il int rd()
{
int x=0,w=1;char ch=0;
while(ch<'0'||ch>'9'){if(ch=='-') w=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
return x*w;
}
struct point
{
db x,y;
bool o;
point(){}
point(db nx,db ny,char ch){x=nx,y=ny,o=ch=='R';}
bool operator < (const point &bb) const {return y!=bb.y?y<bb.y:x<bb.x;}
point operator - (const point &bb) const {return point(x-bb.x,y-bb.y,0);}
db operator * (const point &bb) const {return x*bb.y-y*bb.x;}
}a[N];
il db sq(db x){return x*x;}
il db dis(point aa,point bb){return sqrt(sq(aa.x-bb.x)+sq(aa.y-bb.y));}
int n;
bool o[N];
int s[N],t,m;
struct line
{
int x,y;
db k;
bool operator < (const line &bb) const {return k<bb.k;}
}li[N*N];
struct node
{
int sm,s,ls,rs;
node(){sm=s=ls=rs=0;}
node(bool o){sm=o?1:-(1<<20),s=ls=rs=o;}
node operator + (const node &bb) const
{
node an;
an.sm=sm+bb.sm;
an.s=max(max(s,bb.s),rs+bb.ls);
an.ls=max(ls,sm+bb.ls);
an.rs=max(bb.rs,bb.sm+rs);
return an;
}
}tr[N<<2];
int rk[N],p[N];
void bui(int o,int l,int r)
{
if(l==r){tr[o]=node(a[l].o),p[l]=o;return;}
int mid=(l+r)>>1;
bui(o<<1,l,mid),bui(o<<1|1,mid+1,r);
tr[o]=tr[o<<1]+tr[o<<1|1];
}
il void modif(int x,int y)
{
int o=p[x];
tr[o]=node(y),o>>=1;
while(o) tr[o]=tr[o<<1]+tr[o<<1|1],o>>=1;
}
int main()
{
n=rd();
char cc[2];
for(int i=1;i<=n;++i)
{
scanf("%lf%lf",&a[i].x,&a[i].y);
scanf("%s",cc);
a[i]=point(a[i].x,a[i].y,cc[0]);
}
sort(a+1,a+n+1);
for(int i=1;i<=n;++i)
for(int j=i+1;j<=n;++j)
li[++m]=(line){i,j,fabs(a[i].x-a[j].x)>eps?(a[i].y-a[j].y)/(a[i].x-a[j].x):1e30};
sort(li+1,li+m+1);
bui(1,1,n);
for(int i=1;i<=n;++i) rk[i]=i;
int ans=tr[1].s;
for(int i=upper_bound(li+1,li+m+1,(line){0,0,-1e-30})-li;i<=m;++i)
{
int x=li[i].x,y=li[i].y;
modif(rk[x],a[y].o),modif(rk[y],a[x].o);
swap(rk[x],rk[y]);
ans=max(ans,tr[1].s);
}
bui(1,1,n);
for(int i=1;i<=n;++i) rk[i]=i;
for(int i=lower_bound(li+1,li+m+1,(line){0,0,0})-li-1;i;--i)
{
int x=li[i].x,y=li[i].y;
modif(rk[x],a[y].o),modif(rk[y],a[x].o);
swap(rk[x],rk[y]);
ans=max(ans,tr[1].s);
}
printf("%d
",ans);
return 0;
}