「JOISC 2014 Day3」稻草人
Solution
对于一个点 (A)，能与其组成答案的点 (B)，必然不存在另一点 (C)，其在 (A,B) 所组成的矩形之中。
二维题目的一个常用 trick：按一维排序后作为时间轴，降为一维。
如果按 (x) 排序之后按 (y) 插入每一个点，问题变为区间最大后缀个数，这个是区间单调栈的经典。
时间复杂度 (O(nlog^2n))。
Code
const int N=2e5;
struct Point {
int x,y;
} a[N+10];
int lsh[N+10];
bool cmp(Point a,Point b) {
return a.y<b.y;
}
ll ans;
int ma[N*4+10],cnt[N*4+10];
int calc(int p,int l,int r,int x) {
if(l==r) return ma[p]>x;
int mid=(l+r)>>1;
if(ma[p*2+1]>x) return cnt[p]-cnt[p*2+1]+calc(p*2+1,mid+1,r,x);
return calc(p*2,l,mid,x);
}
void pushup(int p,int l,int r) {
ma[p]=ma[p*2+1],cnt[p]=cnt[p*2+1];
int mid=(l+r)>>1;
cnt[p]+=calc(p*2,l,mid,ma[p]);
chkmax(ma[p],ma[p*2]);
}
void update(int p,int l,int r,int x,int v) {
if(l==r) {cnt[p]=1,ma[p]=v;return;}
int mid=(l+r)>>1;
if(x<=mid) update(p*2,l,mid,x,v);
else update(p*2+1,mid+1,r,x,v);
pushup(p,l,r);
}
pii query(int p,int l,int r,int x,int y) {
if(x<=l&&r<=y) return mp(cnt[p],ma[p]);
int mid=(l+r)>>1;
if(y<=mid) return query(p*2,l,mid,x,y);
pii res=query(p*2+1,mid+1,r,x,y);
res.fi+=calc(p*2,l,mid,res.se);
chkmax(res.se,ma[p*2]);
return res;
}
int main() {
int n,tot=0;
scanf("%d",&n);
for(int i=1;i<=n;i++) {
scanf("%d %d",&a[i].x,&a[i].y);
a[i].y++,lsh[++tot]=a[i].x;
}
sort(lsh+1,lsh+tot+1);
for(int i=1;i<=n;i++) a[i].x=lower_bound(lsh+1,lsh+tot+1,a[i].x)-lsh;
sort(a+1,a+n+1,cmp);
for(int i=1;i<=n;i++) {
ans=(ans+(ll)query(1,1,n,1,a[i].x).fi);
update(1,1,n,a[i].x,a[i].y);
}
printf("%lld
",ans);
}
「JOISC 2014 Day4」两个人的星座
Solution
考虑枚举内公切线。
固定内公切线的一点，将每个点极角排序，初始时以内公切线为极轴，统计上方和下方的点，就可以统计答案。
考虑转极轴，因为是内公切线，那么可以快速统计答案。
注意最后每个三角形被算了 (4) 次，记得减去。
Code
const int N=3e4;
struct Point {
int x,y,c;
Point(){}
Point(int _x,int _y,int _c=0):
x(_x),y(_y),c(_c) {}
void get() {scanf("%d %d %d",&x,&y,&c);}
bool where() {return y<0||(!y&&x<0);}
};
Point operator + (Point a,Point b) {
return Point(a.x+b.x,a.y+b.y);
}
Point operator - (Point a,Point b) {
return Point(a.x-b.x,a.y-b.y,a.c);
}
ll operator * (Point a,Point b) {
return 1ll*a.x*b.y-1ll*a.y*b.x;
}
bool operator < (Point a,Point b) {
if(a.where()!=b.where()) return a.where()<b.where();
return a*b>0;
}
Point a[N+10],b[N*2+10];
int cnt[2][3];
int main() {
ll ans=0;
int n;scanf("%d",&n);
for(int i=1;i<=n;i++) a[i].get();
for(int I=1;I<=n;I++) {
int m=0;memset(cnt,0,sizeof cnt);
for(int i=1;i<=n;i++)
if(i!=I) {
b[++m]=a[i]-a[I];
++cnt[0][b[m].c];
}
sort(b+1,b+m+1);
for(int i=1;i<=m;i++) b[i+m]=b[i];
for(int i=1,j=1;i<=m;i++) {
if(j==i) {
--cnt[0][b[j].c],++cnt[1][b[j].c];
j++;
}
while(j<i+m&&b[i]*b[j]>0) {
--cnt[0][b[j].c],++cnt[1][b[j].c];
j++;
}
--cnt[1][b[i].c];
ll s1=1,s2=1;
for(int k=0;k<3;k++) {
if(k!=a[I].c) s1*=cnt[0][k],s2*=cnt[1][k];
if(k!=b[i].c) s1*=cnt[1][k],s2*=cnt[0][k];
}
ans+=s1+s2;
++cnt[0][b[i].c];
}
}
printf("%lld
",ans/4);
}