[COCI2009]Dvapravca
先给出考场上的(O(n^3))乱搞方法：枚举一个蓝点和一个红点，找出过着两个点的直线，再枚举蓝点找出这条直线最多能往两边扩展多宽，最后枚举红点计算贡献。
注意在确定一条直线能往两边扩展多宽时不要求点到直线的距离，否则常数会太大，只要求竖直方向的距离就可以了。正确性显然，具体看代码。
现在有个重要的问题，求大佬来解决：如果直接这样写会被卡到65到70分，但是如果把蓝点和红点按(x)为第一关键字(y)为第二关键字从小到大排个序，就能得到90至100分（考试时用的评测机能跑到90分，洛谷神机上能切）。然而我不会证明这样究竟优化在哪里，求大佬证明。
#include<cstdio>
#include<algorithm>
#define R register
#define I inline
#define D double
using namespace std;
const int N=1003,inf=0x3f3f3f3f;
struct V{int x,y;}r[N],b[N];
struct L{D k,b;}f;
I int operator<(V a,V b){return a.x^b.x?a.x<b.x:a.y<b.y;}
I D min(D x,D y){return x<y?x:y;}
I int max(int x,int y){return x>y?x:y;}
I L lin(V a,V b){
if(a.x==b.x)
return (L){inf,0};
D k=(D)(b.y-a.y)/(b.x-a.x);
return (L){k,(D)a.y-k*a.x};
}
I D dst(V a){return f.k*a.x+f.b-a.y;}
int main(){
R int n,x,y,i,j,t,p=0,q=0,g,h,o=0;
R char c[2];
D d,u,v;
scanf("%d",&n);
for(i=1;i<=n;++i){
scanf("%d%d%s",&x,&y,c);
if(c[0]=='R')
r[++p]=(V){x,y};
else
b[++q]=(V){x,y};
}
sort(b+1,b+q+1),sort(r+1,r+p+1);//就是这里，不加会慢很多
for(i=1;i<=q;++i)
for(j=1;j<=p;++j){
f=lin(b[i],r[j]),u=v=inf,g=h=1;
for(t=1;t<=q;++t)
if(t^i)
if((d=dst(b[t]))>0)
u=min(u,d);
else
v=min(v,-d);
for(t=1;t<=p;++t)
if(t^j)
if((d=dst(r[t]))>0)
g+=d<u;
else
h+=-d<v;
o=max(o,max(g,h));
}
printf("%d",o);
return 0;
}
亲测如果没加sort应该是过不了的，xzz大神仙尝试把坐标系随机旋转了一下，变得更快了。所以这道题告诉我们一个经验：碰见不会的计算几何题，先随机旋转坐标系，再把点排一遍序，打起暴力更有自信！
还是放一下正解(O(n^2 log n))的做法吧。考虑如果要求直线垂直于(x)轴，那么如果把点按刚才所说的排一遍序，要求的就是序列上连续的最长的(1)的个数（如果把红色视作(1)）。由于直线可以倾斜，考虑旋转坐标系，当某两个点连线的斜率与当前(y)轴在原坐标系中的斜率相等时，这两个点在序列上的位置就会交换，这下可以用线段树来维护，由于最多交换(O(n^2))次顺序，复杂度是(O(n^2 log n))。
#include<cstdio>
#include<algorithm>
#define R register
#define I inline
#define D double
using namespace std;
const int N=1003,M=1000003,S=4003;
int f[N],n;
struct T{int f,l,r,d;}e[S];
struct V{int x,y,c;}p[N];
struct L{D k; int x,y;}q[M];
I int operator<(V a,V b){return a.x^b.x?a.x<b.x:a.y<b.y;}
I int operator<(L a,L b){return a.k>b.k;}
I int max(int x,int y){return x>y?x:y;}
I T operator+(T x,T y){
T z;
z.f=max(x.r+y.l,max(x.f,y.f)),z.d=x.d+y.d;
if(x.l==x.d)
z.l=x.d+y.l;
else
z.l=x.l;
if(y.r==y.d)
z.r=x.r+y.d;
else
z.r=y.r;
return z;
}
I void swp(int&x,int&y){x^=y,y^=x,x^=y;}
I void upd(int k,int v){e[k]=(T){v,v,v,1};}
I void bld(int k,int l,int r){
if(l==r){
upd(k,p[l].c);
return ;
}
R int p=k<<1,q=p|1,m=l+r>>1;
bld(p,l,m),bld(q,m+1,r),e[k]=e[p]+e[q];
}
void mdf(int k,int l,int r,int x,int v){
if(l==r){
upd(k,v);
return ;
}
R int p=k<<1,q=p|1,m=l+r>>1;
if(x<=m)
mdf(p,l,m,x,v);
else
mdf(q,m+1,r,x,v);
e[k]=e[p]+e[q];
}
int main(){
R int i,j,x,y,t=0,o;
R char c[2];
scanf("%d",&n);
for(i=1;i<=n;++i){
scanf("%d%d%s",&x,&y,c);
if(c[0]=='R')
p[i]=(V){x,y,1};
else
p[i]=(V){x,y,0};
}
sort(p+1,p+n+1);
for(i=1;i<=n;++i)
f[i]=i;
for(i=1;i<n;++i)
for(j=i+1;j<=n;++j)
q[++t]=(L){(D)(p[j].y-p[i].y)/(p[j].x-p[i].x),i,j};
sort(q+1,q+t+1),bld(1,1,n),o=e[1].f;
for(i=1;i<=t;++i){
x=f[q[i].x],y=f[q[i].y],swp(f[q[i].x],f[q[i].y]);
if(p[x].c^p[y].c)
swp(p[x].c,p[y].c),mdf(1,1,n,x,p[x].c),mdf(1,1,n,y,p[y].c),o=max(o,e[1].f);
}
printf("%d",o);
return 0;
}