luoguP4385 [COCI2009]Dvapravca

luoguP4385 [COCI2009]Dvapravca

原题传送门:>Here<

我们考虑随机选两个点,然后连一条经过这两个点的直线,并向两边扩展。做10000组就可以AC了。

以上是乱搞做法。

我们考虑当平行线平行于$x$轴时怎么办。

在这种情况下,我们只要把点投影到$y$轴上,然后查询最长连续红点就可以了。

其实绝对位置不重要,所以我们只要把点对纵坐标排序就行了。

现在我们考虑旋转平行线。

每次我们只需要把点投影到与平行线垂直的直线上,然后查询最长连续红点。

我们发现旋转平行线时,当两个点构成的直线与平行线平行时,也就说明这两个点的投影重合。那么在旋转前后,两个点的位置会进行交换。

这可以用线段树来维护。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include <cstdio>
#include <algorithm>

using std::sort;
using std::swap;
using std::max;

struct point{
int x,y;
bool type;
bool operator<(point rhs)const{return y!=rhs.y?y<rhs.y:x<rhs.x;}
}a[1001];
struct line{
int a,b;
double slope;
bool operator<(line rhs)const{return slope<rhs.slope;}
}lines[1000001];
int n,top;
bool get(){
char ch=getchar();
while(ch!='R'&&ch!='B')ch=getchar();
return ch=='R';
}
int L[100001],R[100001],len[100001],size[100001],num[100001],val[100001];
void pushup(int root){
L[root]=(L[root<<1]==size[root<<1])?(L[root<<1]+L[root<<1|1]):(L[root<<1]);
R[root]=(R[root<<1|1]==size[root<<1|1])?(R[root<<1|1]+R[root<<1]):(R[root<<1|1]);
len[root]=max(len[root<<1],max(len[root<<1|1],R[root<<1]+L[root<<1|1]));
}
void build(int root,int l,int r){
size[root]=r-l+1;
if(l==r){
L[root]=R[root]=len[root]=a[l].type;
return;
}
build(root<<1,l,(l+r)>>1);
build(root<<1|1,((l+r)>>1)+1,r);
pushup(root);
}
void update(int root,int l,int r,int e,int x){
if(l==r){
L[root]=R[root]=len[root]=x;
return;
}
if((l+r)>>1>=e)update(root<<1,l,(l+r)>>1,e,x);
else update(root<<1|1,((l+r)>>1)+1,r,e,x);
pushup(root);
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d%d",&a[i].x,&a[i].y);
a[i].type=get();
}
sort(a+1,a+n+1);
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++)
lines[++top]=(line){i,j,(a[i].x!=a[j].x)?((double)(a[i].y-a[j].y)/(double)(a[i].x-a[j].x)):1e18};
sort(lines+1,lines+top+1);
int l=1,r=top,mid,ans=top+1;
while(l<=r){
mid=(l+r)>>1;
if(lines[mid].slope>(-1e-18))ans=mid,r=mid-1;
else l=mid+1;
}
build(1,1,n);
int tot=len[1];
for(int i=1;i<=n;i++)num[i]=i;
for(int i=ans;i<=top;i++){
int x=lines[i].a,y=lines[i].b;
update(1,1,n,num[x],a[y].type);
update(1,1,n,num[y],a[x].type);
tot=max(tot,len[1]);
swap(num[x],num[y]);
}
build(1,1,n);
for(int i=1;i<=n;i++)num[i]=i;
l=1,r=top,ans=0;
while(l<=r){
mid=(l+r)>>1;
if(lines[mid].slope>=0.)ans=mid,r=mid-1;
else l=mid+1;
}
for(int i=ans-1;i;i--){
int x=lines[i].a,y=lines[i].b;
update(1,1,n,num[x],a[y].type);
update(1,1,n,num[y],a[x].type);
tot=max(tot,len[1]);
swap(num[x],num[y]);
}
printf("%d\n",tot);
}

Comments

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×