省队集训day6 C

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

Sample Output

先考虑一下如果这两条直线必须与x轴垂直怎么做，我们先可以将所有点按x为第一关键字，y为第二关键字排序，在这个排好序的序列中找到最长的一段红色就是答案了（用线段树维护）

然后我们把坐标系旋转，如果y轴扫过了两点连成的直线，则这两个点的排名就会交换，旋转一周交换的点对为O（N²)个,所以可以用一个线段树来维护区间最长红点数，支持单点修改和查询，复杂度O（N²logN）。

code：

 1 #include<cstdio> 
 2 #include<iostream> 
 3 #include<cstring> 
 4 #include<algorithm> 
 5 #define maxn 1005 
 6 using namespace std; 
 7 int n,m,a,b,ans,pos[maxn]; 
 8 char s[2]; 
 9 inline int min(const int &a,const int &b){  
10   int diff=b-a;  
11   return a+(diff&(diff>>31));  
12 }  
13 inline int max(const int &a,const int &b){  
14   int diff=b-a;  
15   return b-(diff&(diff>>31));  
16 } 
17 struct Point{ 
18     int x,y,col; 
19 }point[maxn]; 
20 inline bool cmp1(Point a,Point b){ 
21     if (a.x!=b.x) return a.x<b.x; 
22     return a.y<b.y;   
23 } 
24 struct Line{ 
25     int a,b,x,y; 
26 }line[maxn*maxn]; 
27 inline bool cmp2(const Line &a,const Line &b){return 1LL*a.x*b.y<1LL*a.y*b.x;} 
28 inline bool cmp(const Line &a,const Line &b){return 1LL*a.x*b.y==1LL*a.y*b.x;} 
29 struct Seg{ 
30     #define ls k<<1 
31     #define rs (k<<1)+1 
32     int val[maxn<<2],lmax[maxn<<2],rmax[maxn<<2],col[maxn<<2]; 
33     inline void update(int k){ 
34         col[k]=col[ls]|col[rs]; 
35         lmax[k]=(col[ls])?lmax[ls]:lmax[ls]+lmax[rs]; 
36         rmax[k]=(col[rs])?rmax[rs]:rmax[ls]+rmax[rs]; 
37         val[k]=max(rmax[ls]+lmax[rs],max(val[ls],val[rs])); 
38     } 
39     inline void modify(int k,int l,int r,int x,int c){ 
40         if (l==r){val[k]=lmax[k]=rmax[k]=c^1,col[k]=c;return;} 
41         int m=(l+r)>>1; 
42         if (x<=m) modify(ls,l,m,x,c); else modify(rs,m+1,r,x,c); 
43         update(k); 
44     } 
45 }T; 
46 int main(){ 
47     scanf("%d",&n); 
48     for (int i=1;i<=n;i++){ 
49         scanf("%d%d%s",&point[i].x,&point[i].y,s); 
50         point[i].col=(s[0]=='B'),pos[i]=i; 
51     } 
52     sort(point+1,point+n+1,cmp1); 
53     for (int i=1;i<=n;i++) for (int j=i+1;j<=n;j++)  
54         line[++m]=(Line){i,j,point[j].x-point[i].x,point[j].y-point[i].y}; 
55     sort(line+1,line+m+1,cmp2); 
56     for (int i=1;i<=n;i++) T.modify(1,1,n,i,point[i].col); 
57     ans=T.val[1]; 
58     for (int i=1,j=1;i<=m;i=j){ 
59         for (;j<=m&&cmp(line[i],line[j]);j++){ 
60             a=line[j].a,b=line[j].b; 
61             T.modify(1,1,n,pos[b],point[a].col); 
62             T.modify(1,1,n,pos[a],point[b].col); 
63             swap(pos[a],pos[b]); 
64             ans=max(ans,T.val[1]); 
65         } 
66     } 
67     printf("%d
",ans); 
68     return 0; 
69 }