首页 > 代码库 > bzoj3086: Coci2009 dvapravca

bzoj3086: Coci2009 dvapravca

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=0,ans=0;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[1007];struct ev{    pos x;    int a,b;    bool operator<(const ev&w)const{return x*w.x<0;}}es[1007*507];char str[4];int ls[2111],rs[2111],ms[2111],ws[2111],sz[2111];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+=1023,ls[w]=rs[w]=ms[w]=v,w>>=1;w;w>>=1)up(w,w<<1,w<<1^1);}int main(){    scanf("%d",&n);    for(int i=1;i<=n;++i){        scanf("%d%d%s",&ps[i].a.x,&ps[i].a.y,str);        ps[i].col=str[0]==R;    }    std::sort(ps+1,ps+n+1);    for(int i=1;i<=n;++i){        for(int j=1;j<=n;++j){            pos w=ps[j].a-ps[i].a;            if(w.y>0||w.y==0&&w.x>0)es[ep++]=(ev){w,i,j};        }    }    for(int i=1;i<=n;++i){        ws[i]=i;        sz[i+1023]=1;        if(ps[i].col)ls[i+1023]=rs[i+1023]=ms[i+1023]=1;    }    for(int i=1023;i;--i)sz[i]=sz[i<<1]+sz[i<<1^1],up(i,i<<1,i<<1^1);    ans=ms[1];    std::sort(es,es+ep);    for(int i=0,j=0;i<ep;){        for(;j<ep&&es[i].x*es[j].x==0;++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[1]);    }    printf("%d",ans);    return 0;}

 

bzoj3086: Coci2009 dvapravca