9
4
2016
0

[BZOJ3295] [Cqoi2011]动态逆序对

本来想用树状数组+主席树水过去的……20min码完后发现空间炸了

卡了几发空间后发现自己并不会卡空间的高明技巧就弃疗了

后来写了一个CDQ分治就水过去了

主席树做法就不说了

CDQ分治主要就是按照位置划分第一层,按照时间(操作顺序)划分第二层,按照值划分第三层

第一层我们读入进来的就是有序的所以不用管

第二次我们可以用CDQ分治分治第二层

分治时用树状数组统计第三层

最后递归前要还原树状数组

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=200005;

int L[N],R[N],BIT[N],time,n,m,pos[N];
long long ans[N];

inline void Read(int &x){
char ch;
while((ch=getchar())<'0' || ch>'9');
x=ch-'0';
while((ch=getchar())>='0' && ch<='9')x=x*10+ch-'0';
}

struct Operation{
int t,a,b;
}a[N],b[N];

inline int lowbit(const int &x){return x&(-x);}
inline void Add(int x,int y){while(x<=n){BIT[x]+=y;x+=lowbit(x);}}
inline int Sum(int x){int ans=0;while(x){ans+=BIT[x];x-=lowbit(x);}return ans;}

void CDQ(int l,int r){
if(l>=r)return;
int mid=l+r>>1;
int Lx=l,Rx=mid+1;
for(register int i=l;i<=r;i++){
	if(a[i].t<=mid)b[Lx++]=a[i];
	else b[Rx++]=a[i];
}
Lx=l,Rx=mid;
for(register int i=mid+1;i<=r;i++){
	for(;Lx<=mid && b[Lx].a<=b[i].a;Lx++)Add(b[Lx].b,1);
	L[b[i].t]+=Lx-l-Sum(b[i].b);
}
for(register int i=l;i<Lx;i++)Add(b[i].b,-1);
for(register int i=r;i>mid;i--){
	for(;Rx>=l && b[Rx].a>b[i].a;Rx--)Add(b[Rx].b,1);
	R[b[i].t]+=Sum(b[i].b-1);
}
for(register int i=Rx+1;i<=mid;i++)Add(b[i].b,-1);
for(register int i=l;i<=r;i++)a[i]=b[i];
CDQ(l,mid);CDQ(mid+1,r);
}

int main(){
freopen("3295.in","r",stdin);
freopen("3295.out","w",stdout);
Read(n);Read(m);time=n;
for(register int i=1;i<=n;i++)Read(a[i].b),a[i].a=i,pos[a[i].b]=i;
for(register int i=1;i<=m;i++){int x;Read(x);a[pos[x]].t=time--;}
for(register int i=1;i<=n;i++)if(!a[i].t)a[i].t=time--;
CDQ(1,n);
for(register int i=1;i<=n;i++)ans[i]=ans[i-1]+L[i]+R[i];
for(register int i=n;i>=n-m+1;i--)printf("%lld\n",ans[i]);
return 0;
}
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=100005;

int n,m,BIT[N],cnt,a[N],b[N],ls[N*108],rs[N*108],sum[N*108],q[N],bq[N],pts;
long long ans,an[N];

inline void Read(int &x){
char ch;
while((ch=getchar())<'0' || ch>'9');
x=ch-'0';
while((ch=getchar())>='0' && ch<='9')x=(x<<3)+(x<<1)+ch-'0';
}

inline void Pushup(const int &rt){sum[rt]=sum[ls[rt]]+sum[rs[rt]];}

void Insert(int &rt,int lrt,int l,int r,int v){
rt=++cnt;
sum[rt]=sum[lrt]+1;
ls[rt]=ls[lrt];
rs[rt]=rs[lrt];
if(l==r)return;
int mid=l+r>>1;
if(v<=mid)Insert(ls[rt],ls[lrt],l,mid,v);
if(v>mid)Insert(rs[rt],rs[lrt],mid+1,r,v);
Pushup(rt);
}

void Delete(int &rt,int lrt,int l,int r,int v){
rt=++cnt;
sum[rt]=sum[lrt]-1;
ls[rt]=ls[lrt];
rs[rt]=rs[lrt];
if(l==r)return;
int mid=l+r>>1;
if(v<=mid){if(sum[ls[rt]]==1){ls[rt]=0;return;}Delete(ls[rt],ls[lrt],l,mid,v);}
if(v>mid){if(sum[rs[rt]]==1){rs[rt]=0;return;}Delete(rs[rt],rs[lrt],mid+1,r,v);}
Pushup(rt);
}

long long FindU(int rt,int l,int r,int v){
if(l==r)return 0;
int mid=l+r>>1;
if(v<=mid)return sum[rs[rt]]+FindU(ls[rt],l,mid,v);
return FindU(rs[rt],mid+1,r,v);
}

long long FindD(int rt,int l,int r,int v){
if(l==r)return 0;
int mid=l+r>>1;
if(v<=mid)return FindD(ls[rt],l,mid,v);
return sum[ls[rt]]+FindD(rs[rt],mid+1,r,v);
}

inline int lowbit(const int &x){return x&(-x);}
inline void Add(int x,int y){while(x<=n){Insert(BIT[x],BIT[x],1,n,y);x+=lowbit(x);}}
inline void Del(int x,int y){while(x<=n){Delete(BIT[x],BIT[x],1,n,y);x+=lowbit(x);}}
inline long long SumU(int x,int y){long long ans=0;while(x){ans+=FindU(BIT[x],1,n,y);x-=lowbit(x);}return ans;}
inline long long SumD(int x,int y){long long ans=0;while(x){ans+=FindD(BIT[x],1,n,y);x-=lowbit(x);}return ans;}

int main(){
freopen("3295.in","r",stdin);
freopen("3295.out","w",stdout);
Read(n);Read(m);
for(register int i=1;i<=n;i++){Read(a[i]);b[a[i]]=i;}
for(register int i=1;i<=m;i++){Read(q[i]);bq[q[i]]=1;}
for(register int i=1;i<=n;i++){
	if(bq[a[i]])continue;
	Add(i,a[i]);
	ans+=SumU(i,a[i])+SumD(n,a[i])-SumD(i-1,a[i]);
}
an[++pts]=ans;
for(register int i=m;i;i--){
	Add(b[q[i]],q[i]);
	ans+=SumU(b[q[i]],q[i])+SumD(n,q[i])-SumD(b[q[i]]-1,q[i]);
    an[++pts]=ans;
}
for(register int i=pts;i>1;i--)printf("%lld\n",an[i]);
return 0;
}
Category: BZOJ | Tags: OI bzoj
8
24
2016
0

[BZOJ3757] 苹果树

怎么交都是RE

找来hzwer的程序RE

找来PoPoQQQ的程序RE

找来ww140142的程序RE

一开始我还以为自己写错了

毁我AC率

-------------------------

树上莫队

我没用王室联邦的分块方法,我写了一个块状树的版本

目前莫名RE

等我要到数据再修复……

-------------------------

本机怎么测都AC(Lemon)

以为是爆栈了写个手工栈照样RE

把数组放大10倍还是RE

不管了

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=50005,M=100005,block_size=300,T=17;

int n,m,color[N],en,h[N],belong[N],cnt[N],dfn[N],indexs[N],colornum,dep[N],L,R,fa[N][20],Index,siz[N],block_cnt,ans[N],root;

inline void Read(int &x){
char ch;
while((ch=getchar())<'0' || ch>'9');
x=ch-'0';
while((ch=getchar())>='0' && ch<='9')x=x*10+ch-'0';
}

struct Edge{
int b,next;
}e[M];

struct Queries{
int l,r,a,b,id;
friend inline bool operator<(const Queries &A,const Queries &B){return belong[A.l]<belong[B.l] || (belong[A.l]==belong[B.l] && dfn[A.r]<dfn[B.r]);}
}que[M];

inline void AddEdge(const int &sa,const int &sb){e[++en].b=sb;e[en].next=h[sa];h[sa]=en;}

inline void Add(const int &x){cnt[x]++;if(cnt[x]==1)colornum++;}
inline void Del(const int &x){cnt[x]--;if(cnt[x]==0)colornum--;}
inline void Change(const int &x){if(indexs[x])Del(color[x]);else Add(color[x]);indexs[x]^=1;}

void dfs(int u,int f){
dfn[u]=++Index;fa[u][0]=f;
if(siz[belong[f]]==block_size)belong[u]=++block_cnt;
else belong[u]=belong[f];
siz[belong[u]]++;dep[u]=dep[f]+1;
for(int i=h[u];i;i=e[i].next){
    int v=e[i].b;
    if(v==f)continue;
    dfs(v,u);
}
}

inline void Prepare(){
for(register int i=1;i<=T;i++){
    for(register int j=1;j<=n;j++)fa[j][i]=fa[fa[j][i-1]][i-1];
}
}

inline int LCA(int u,int v){
if(dep[u]<dep[v])swap(u,v);
int deep=dep[u]-dep[v];
for(register int i=T;~i;i--)if(deep&(1<<i))u=fa[u][i];
for(register int i=T;~i;i--)if(fa[u][i]!=fa[v][i])u=fa[u][i],v=fa[v][i];
return u==v?u:fa[u][0];
}

int main(){
freopen("3757.in","r",stdin);
freopen("3757.out","w",stdout);
Read(n);Read(m);
for(register int i=1;i<=n;i++)Read(color[i]);
for(register int i=1;i<=n;i++){int u,v;Read(u);Read(v);if(u==0 || v==0)root=u+v;else AddEdge(u,v),AddEdge(v,u);}
dfs(root,0);
Prepare();
for(register int i=1;i<=m;i++){
    Read(que[i].l);Read(que[i].r);Read(que[i].a);Read(que[i].b);que[i].id=i;
    if(dfn[que[i].l]>dfn[que[i].r])swap(que[i].l,que[i].r);
}
sort(que+1,que+m+1);L=R=root;
for(register int i=1;i<=m;i++){
    int y=LCA(que[i].l,L);
	for(int j=que[i].l;j!=y;j=fa[j][0])Change(j);
	for(int j=L;j!=y;j=fa[j][0])Change(j);
	y=LCA(que[i].r,R);
	for(int j=que[i].r;j!=y;j=fa[j][0])Change(j);
	for(int j=R;j!=y;j=fa[j][0])Change(j);
	L=que[i].l;R=que[i].r;
    int x=LCA(L,R);
    Change(x);
    ans[que[i].id]=colornum;
    if(cnt[que[i].a] && cnt[que[i].b] && que[i].a!=que[i].b)ans[que[i].id]--;
    Change(x);
}
for(register int i=1;i<=m;i++)printf("%d\n",ans[i]);
return 0;
}
Category: BZOJ | Tags: OI bzoj
8
21
2016
0

[BZOJ3036] 绿豆蛙的归宿

考虑dp

设$d[x]$为到达$x$号点时的期望长度

因为会随机选一个点,所以到达$x$号点的期望长度为所有能到x号点的点的期望长度乘以到达x号点的边长度

这就告诉我们需要拓扑排序

首先边反向(这样不用处理根本到不了终点的点,而且可以避免计算错误)

(当然反向是比正向快多了)(我正向TLE了)

然后直接在拓扑序上面搞就行

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;

const int N=100005;

int n,m,h[N],en,nxt[N];
double d[N],p[N];
queue<int> Q;

inline void Read(int &x){
char ch;
while((ch=getchar())<'0' || ch>'9');
x=ch-'0';
while((ch=getchar())>='0' && ch<='9')x=x*10+ch-'0';
}

struct Edge{int b,v,next;}e[N<<1];
inline void AddEdge(const int &sa,const int &sb,const int &sc){e[++en].b=sb;nxt[sb]++;e[en].v=sc;e[en].next=h[sa];h[sa]=en;}

inline void bfs(){
for(register int i=1;i<=n;i++)p[i]=1.0/nxt[i];
Q.push(n);
while(!Q.empty()){
	int u=Q.front();Q.pop();
	for(register int i=h[u];i;i=e[i].next){
		int v=e[i].b;
		d[v]+=p[v]*(d[u]+e[i].v);
		if(!--nxt[v])Q.push(v);
	}
}
}

int main(){
freopen("3036.in","r",stdin);
freopen("3036.out","w",stdout);
Read(n);Read(m);
for(register int i=1;i<=m;i++){
	int u,v,w;
    Read(u);Read(v);Read(w);
    AddEdge(v,u,w);
}
bfs();
printf("%.2lf\n",d[1]);
return 0;
}
Category: BZOJ | Tags: OI bzoj
8
20
2016
0

[BZOJ1419] Red is good

设$dp[i][j]$为有i张红j张黑时的期望最大值

因为随时可以停止所以当期望小于0时直接改成0

同时因为会爆空间所以改成滚动数组

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=5005;

int R,B;
double dp[2][N];

inline void Read(int &x){
char ch;
while((ch=getchar())<'0' || ch>'9');
x=ch-'0';
while((ch=getchar())>='0' && ch<='9')x=x*10+ch-'0';
}

int main(){
freopen("1419.in","r",stdin);
freopen("1419.out","w",stdout);
Read(R);Read(B);
for(register int i=1;i<=R;i++){
	int now=i&1,pre=now^1;
	dp[now][0]=i;
	for(register int j=1;j<=B;j++){
		double Px=1.0*i/(i+j);
		dp[now][j]=Px*(dp[pre][j]+1)+(1-Px)*(dp[now][j-1]-1);
		if(dp[now][j]<0)dp[now][j]=0;
	}
}
printf("%.6lf\n",dp[R&1][B]-0.0000005);
return 0;
}
Category: BZOJ | Tags: OI bzoj
8
20
2016
0

[BZOJ3809] Gty的二逼妹子序列

明天就要上课了

这题是一个莫队+分块

据说莫队+树状数组会T掉

所以我就把整个答案按照权值分块卡卡常就做完了

目前bzoj用时为$20808ms$

数组开小wa两次我真是太弱了

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=100005,block=300;

int n,m,s[N],ans[N*10],cnt[N],bk[N];

inline void Read(int &x){
char ch;
while((ch=getchar())<'0' || ch>'9');
x=ch-'0';
while((ch=getchar())>='0' && ch<='9')x=x*10+ch-'0';
}

inline int Gi(const int &x){return (x-1)/block+1;}

struct Query{
int l,r,a,b,id;
friend inline bool operator<(const Query &A,const Query &B){return Gi(A.l)<Gi(B.l)||(Gi(A.l)==Gi(B.l) && A.r<B.r);}
}que[N*10];

inline void Up(int x){
cnt[s[x]]++;
if(cnt[s[x]]==1)bk[Gi(s[x])]++;
}

inline void Down(int x){
cnt[s[x]]--;
if(cnt[s[x]]==0)bk[Gi(s[x])]--;
}

inline int Q(const int &l,const int &r){
int ls=Gi(l)+1,rs=Gi(r)-1,lv=Gi(l)*block,rv=(Gi(r)-1)*block+1,ans=0;
if(ls-rs==2)for(register int i=l;i<=r;i++)ans+=(cnt[i]>0);
else {
	for(register int i=ls;i<=rs;i++)ans+=bk[i];
	for(register int i=l;i<=lv;i++)ans+=(cnt[i]>0);
	for(register int i=rv;i<=r;i++)ans+=(cnt[i]>0);
}
return ans;
}

int main(){
freopen("3809.in","r",stdin);
freopen("3809.out","w",stdout);
Read(n);Read(m);
for(register int i=1;i<=n;i++)Read(s[i]);
for(register int i=1;i<=m;i++)Read(que[i].l),Read(que[i].r),Read(que[i].a),Read(que[i].b),que[i].id=i;
sort(que+1,que+m+1);
register int L=1,R=0;
for(register int i=1;i<=m;i++){
	while(L>que[i].l)Up(--L);
	while(L<que[i].l)Down(L++);
	while(R>que[i].r)Down(R--);
	while(R<que[i].r)Up(++R);
    ans[que[i].id]=Q(que[i].a,que[i].b);
}
for(register int i=1;i<=m;i++)printf("%d\n",ans[i]);
return 0;
}
Category: BZOJ | Tags: OI bzoj
8
10
2016
0

[BZOJ3483] SGU505 Prefixes and suffixes(询问在线版)

考虑维护可持久化线段树+字典树

首先建出两个字典树(一正一反),求一下dfs序然后就变成了查询当前字符串在这两个字典树中区间的共有值

我们可以利用可持久化线段树来支持查询

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=2005,M=2000005;

int n,ans,len,posA[N],posB[N],root[N*25],l[N*25],r[N*25],v[N*25],cnt,en,h[M],m;
char s[M],ch;

inline void Read_Decrypt(){
while((ch=getchar())<'a' || ch>'z');
s[len=1]=(ch-'a'+ans)%26;
while((ch=getchar())>='a' && ch<='z')s[++len]=(ch-'a'+ans)%26;
}

struct Edge{
int b,next;
}e[N];

inline void AddEdge(int sa,int sb){e[++en].b=sb;e[en].next=h[sa];h[sa]=en;}

struct Trie{
int son[M][26],cnt,dfn,st[M],ed[M];
inline int ins0();
inline int ins1();
void dfs(int x);
inline pair<int,int> ask0();
inline pair<int,int> ask1();
}A,B;

inline int Trie::ins0(){
int x=0;
for(int i=1;i<=len;i++){
	if(!son[x][s[i]])son[x][s[i]]=++cnt;
	x=son[x][s[i]];
}
return x;
}

inline int Trie::ins1(){
int x=0;
for(int i=len;i;i--){
	if(!son[x][s[i]])son[x][s[i]]=++cnt;
	x=son[x][s[i]];
}
return x;
}

void Trie::dfs(int x){
st[x]=++dfn;
for(int i=0;i<26;i++)if(son[x][i])dfs(son[x][i]);
ed[x]=dfn;
}

inline pair<int,int> Trie::ask0(){
int x=0;
for(int i=1;i<=len;i++){
	if(!son[x][s[i]])return make_pair(0,0);
	x=son[x][s[i]];
}
return make_pair(st[x],ed[x]);
}

inline pair<int,int> Trie::ask1(){
int x=0;
for(int i=len;i;i--){
	if(!son[x][s[i]])return make_pair(0,0);
	x=son[x][s[i]];
}
return make_pair(st[x],ed[x]);
}

inline int Insert(int x,int a,int b,int p){
int y=++cnt;v[y]=v[x]+1;
if(a==b)return y;
int mid=a+b>>1;
if(p<=mid)l[y]=Insert(l[x],a,mid,p),r[y]=r[x];
else l[y]=l[x],r[y]=Insert(r[x],mid+1,b,p);
return y;
}

inline int Query(int x,int a,int b,pair<int,int> p){
if(!x)return 0;
if(p.first<=a && b<=p.second)return v[x];
int mid=a+b>>1,ans=0;
if(p.first<=mid)ans+=Query(l[x],a,mid,p);
if(p.second>mid)ans+=Query(r[x],mid+1,b,p);
return ans;
}

int main(){
freopen("3483.in","r",stdin);
freopen("3483.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++){
    Read_Decrypt();
    posA[i]=A.ins0();posB[i]=B.ins1();
}
A.dfs(0);B.dfs(0);
for(int i=1;i<=n;i++)AddEdge(A.st[posA[i]],B.st[posB[i]]);
for(int i=1;i<=A.dfn;i++){
	root[i]=root[i-1];
	for(int j=h[i];j;j=e[i].next)root[i]=Insert(root[i],1,B.dfn,e[j].b);
}
scanf("%d",&m);
while(m--){
    pair<int,int> L,R;
    Read_Decrypt();
    L=A.ask0();
    Read_Decrypt();
    R=B.ask1();
    if(L.first && R.first)ans=Query(root[L.second],1,B.dfn,R)-Query(root[L.first-1],1,B.dfn,R);
    else ans=0;
    printf("%d\n",ans);
}
return 0;
}
Category: BZOJ | Tags: OI bzoj
8
1
2016
0

[BZOJ1303] [CQOI2009]中位数图

排序完了直接统计就好

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
 
const int N=100005;
 
int n,a[N],b,c[N],d[10*N],e[10*N],pos,ans;
 
void Read(int &x){
char ch;
while((ch=getchar())<'0' || ch>'9');
x=ch-'0';
while((ch=getchar())>='0' && ch<='9')x=x*10+ch-'0';
}
 
int main(){
freopen("1303.in","r",stdin);
freopen("1303.out","w",stdout);
Read(n);Read(b);
for(int i=1;i<=n;i++){Read(a[i]);if(a[i]==b)pos=i,a[i]=0;else a[i]=a[i]>b?1:-1;}
d[n]=1;e[n]=1;
for(int i=pos-1;i;i--){c[i]=c[i+1]+a[i];d[c[i]+n]++;}
for(int i=pos+1;i<=n;i++){c[i]=c[i-1]+a[i];e[c[i]+n]++;}
for(int i=0;i<=2*n-1;i++)ans+=d[i]*e[2*n-i];
printf("%d\n",ans);
return 0;
}
Category: BZOJ | Tags: OI bzoj
8
1
2016
0

[BZOJ4636] 蒟蒻的数列

因为我们只要最后知道答案就好了

所以我们离线

先排序,然后维护一个大根堆然后直接统计就好

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<queue>
#include<algorithm>
using namespace std;
 
const int N=40005;
 
struct Node{
int a,b,k;
Node(){}
Node(int aa,int bb,int kk){a=aa;b=bb;k=kk;}
friend bool operator<(Node A,Node B){return A.a<B.a||(A.a==B.a && A.b<B.b);}
}a[N<<1];
 
class Heap{
private:
priority_queue<int> P,Q;
public:
inline void I(int x){P.push(x);}
inline void D(int x){Q.push(x);}
inline int T(){while(!Q.empty() && Q.top()==P.top())P.pop(),Q.pop();return P.empty()?0:P.top();}
}H;
 
int n,nn;
long long ans;
 
void Read(int &x){
char ch;
while((ch=getchar())<'0' || ch>'9');
x=ch-'0';
while((ch=getchar())>='0' && ch<='9')x=x*10+ch-'0';
}
 
int main(){
freopen("4636.in","r",stdin);
freopen("4636.out","w",stdout);
Read(n);
for(int i=1;i<=n;i++){
    int as,bs,ks;
    Read(as);Read(bs);Read(ks);
    a[++nn]=Node(as,0,ks);
    a[++nn]=Node(bs,1,ks);
}
a[++nn]=Node(0,0,0);
sort(a+1,a+nn+1);
int ft=0;
for(int i=1;i<=nn;i++){
    ans+=1ll*H.T()*(a[i].a-ft);
    ft=a[i].a;
    if(!a[i].b)H.I(a[i].k);
    else H.D(a[i].k);
}
printf("%lld\n",ans);
return 0;
}
Category: BZOJ | Tags: OI bzoj
8
1
2016
0

[BZOJ2618] [Cqoi2006]凸多边形

裸的半平面交

注意特判一下就好了

#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
using namespace std;
 
const int N=50005;
const double eps=1e-17;
 
int n,Pn[15],cnt,first,last;
 
struct Point{
double x,y;
Point(){}
Point(double sa,double sb){x=sa;y=sb;}
friend Point operator+(Point A,Point B){return Point(A.x+B.x,A.y+B.y);}
friend Point operator-(Point A,Point B){return Point(A.x-B.x,A.y-B.y);}
friend Point operator*(Point A,double B){return Point(A.x*B,A.y*B);}
friend double operator*(Point A,Point B){return A.x*B.y-A.y*B.x;}
}poi[15][55],Px[N];
 
struct Line{
Point p,v;
double ang;
Line(){}
Line(Point A,Point B){p=A;v=B-A;ang=atan2(v.y,v.x);}
friend bool operator<(Line A,Line B){return A.ang<B.ang;}
}line[N],*Q[N];
 
double Dist2(Point A,Point B){return (A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y);}
Point GetPoint(Line A,Line B){return A.p+A.v*((B.v*(A.p-B.p))/(A.v*B.v));}
bool OnLeft(Point A,Line B){return (A-B.p)*B.v-eps<=0;}
 
void Intersection(){
first=last=0;
sort(line+1,line+cnt+1);
for(int i=1;i<=cnt;i++){
    while(last-first>=2 && !OnLeft(GetPoint(*Q[last],*Q[last-1]),line[i]))Q[last--]=NULL;
    if(last-first>=1 && fabs(Q[last]->v*line[i].v)<=eps)Q[last]=OnLeft(line[i].p,*Q[last])?line+i:Q[last];
    else Q[++last]=line+i;
}
while(last-first>=2 && !OnLeft(GetPoint(*Q[first+1],*Q[first+2]),*Q[last]))Q[++first]=NULL;
while(last-first>=2 && !OnLeft(GetPoint(*Q[last],*Q[last-1]),*Q[first+1]))Q[last--]=NULL;
}
 
double Area(){
//printf("%d %d\n",first,last);
if(last-first<=1)return 0.0;
Q[last+1]=Q[first+1];
cnt=0;
for(int i=first+1;i<=last;i++){
    Px[++cnt]=GetPoint(*Q[i],*Q[i+1]);
    //printf("%.2lf %.2lf\n",Px[cnt].x,Px[cnt].y);
}
Px[cnt+1]=Px[1];
double Ans=0.0;
for(int i=1;i<=cnt;i++){
    Ans+=Px[i]*Px[i+1];
}
return Ans/2.0;
}
 
int main(){
freopen("2618.in","r",stdin);
freopen("2618.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++){
    scanf("%d",&Pn[i]);
    for(int j=1;j<=Pn[i];j++)scanf("%lf %lf",&poi[i][j].x,&poi[i][j].y);
    poi[i][Pn[i]+1]=poi[i][1];
    for(int j=1;j<=Pn[i];j++)line[++cnt]=Line(poi[i][j],poi[i][j+1]);
}
Intersection();
printf("%.3lf\n",Area());
return 0;
}
Category: BZOJ | Tags: OI bzoj
8
1
2016
0

[BZOJ2458] [BeiJing2011]最小三角形

考虑分治

首先我们按照x轴排序,然后我们要求每段处理时y轴有序

然后排除一些不可能的情况后暴力统计就好了

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
 
const int N=200005;
 
int n;
double ans=1e10;
 
struct Point{
int x,y;
friend bool operator<(Point A,Point B){return A.y<B.y;}
}poi[N],_point[N];
 
bool cmp(Point A,Point B){return A.x<B.x;}
double Abs(int x){return x>0?(double)x:(double)-x;}
double Di(Point A,Point B){return sqrt((double)(A.x-B.x)*(A.x-B.x)+(double)(A.y-B.y)*(A.y-B.y));}
 
void Solve(int l,int r){
if(l==r)return;
if(l+1==r){if(poi[r]<poi[l])swap(poi[l],poi[r]);return;}
int mid=l+r>>1,tp=poi[mid].x;
Solve(l,mid);Solve(mid+1,r);
int l1=l,l2=mid+1;
for(int i=l;i<=r;i++){
    if(l2>r||(l1<=mid && poi[l1]<poi[l2]))_point[i]=poi[l1++];
    else _point[i]=poi[l2++];
}
memcpy(poi+l,_point+l,sizeof(Point)*(r-l+1));
for(int i=l,tail=l;i<=r;i++){
    if(Abs(poi[i].x-tp)<ans/2.0){
        while(poi[i].y-poi[tail].y>ans/2.0)tail++;
        for(int j=tail;j<i-1;j++)if(Abs(poi[j].x-tp)<ans/2.0)if(poi[i].y-poi[j].y<ans/2.0)for(int k=j+1;k<i;k++)ans=min(ans,Di(poi[i],poi[j])+Di(poi[i],poi[k])+Di(poi[j],poi[k]));
    }
}
}
 
int main(){
freopen("2458.in","r",stdin);
freopen("2458.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d %d",&poi[i].x,&poi[i].y);
sort(poi+1,poi+n+1,cmp);
Solve(1,n);
printf("%lf\n",ans);
return 0;
}
Category: BZOJ | Tags: OI bzoj

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com