Home > OI > NOI 2007 货币兑换

NOI 2007 货币兑换


这个题写得烦死人了,要用一棵Splay维护平面点集凸性..

至今仍有两个点TLE,估计是某些操作写猥了

[cc lang=”c++”]
#include
#include
#include
#define MAXN 200100
#define oo 1e8
#define EPS 1e-8
double F[MAXN],A[MAXN],B[MAXN],X[MAXN],Y[MAXN],R[MAXN];
inline double max(double a, double b){
return a>b?a:b;
}
struct splaytree{
struct splaynode{
double x,y;
int s,ok;
splaynode *c[2],*f;
} *root,*null,mempool[MAXN];
int memnum;
void update(splaynode *x){
x->s=x->c[0]->s+x->c[1]->s+1;
}
inline double abs(double x){
return x>=0?x:-x;
}
inline double calc(double A, double B, double x, double y){
return A*x+B*y;
}
inline double slope(double x1, double y1, double x2, double y2){
return (y1-y2)/(x1-x2);
}
inline double cross(double x0, double y0, double x1, double y1, double x2, double y2){
return (x1-x0)*(y2-y0)-(x2-x0)*(y1-y0);
}
inline double cross(splaynode *a, splaynode *b,splaynode *c){
return cross(a->x,a->y,b->x,b->y,c->x,c->y);
}
inline int ok(splaynode *x){
return x->ok;
}
splaynode *newsplaynode(double x, double y, splaynode *f){
splaynode *t=&mempool[memnum++];
t->x=x,t->y=y,t->f=f,t->c[0]=t->c[1]=null,t->s=1,t->ok=1;
return t;
}
void init(){
memnum=0;
null=0;
null=newsplaynode(-oo,-oo,0);
null->s=0;
root=newsplaynode(-oo,-oo,null);
null->ok=root->ok=0;
update(root);
}
void rotate(splaynode *x, int o){
splaynode *y=x->f;
y->c[o]=x->c[!o];
x->c[!o]->f=y;
x->f=y->f;
if(y->f->c[0]==y)
y->f->c[0]=x;
else
y->f->c[1]=x;
y->f=x;
x->c[!o]=y;
update(y);
update(x);
if(root==y) root=x;
}
void splay(splaynode *x, splaynode *f){
if(!ok(x)) return;
while(x->f!=f){
if(x->f->f==f){
if(x==x->f->c[0])
rotate(x,0);
else
rotate(x,1);
}else if(x==x->f->c[0]){
if(x->f==x->f->f->c[0]){
rotate(x->f,0),rotate(x,0);
}else{
rotate(x,0),rotate(x,1);
}
}else{
if(x->f==x->f->f->c[1]){
rotate(x->f,1),rotate(x,1);
}else{
rotate(x,1),rotate(x,0);
}
}
}
}
splaynode *getneighbor(splaynode *x, int o){
splay(x,null);
if(!ok(x)||!ok(x->c[o])) return null;
splaynode *y;
for(y=x->c[o];ok(y->c[!o]);y=y->c[!o]);
return y;
}
void del(splaynode *x){
splay(x,null);
if(!root->c[0]->s){
root=root->c[1];
root->f=null;
return;
}
root->c[0]->f=null;
splaynode *y=root->c[0];
while(y->c[1]->s) y=y->c[1];
y->c[1]=root->c[1],y->c[1]->f=y;
root=root->c[0];
splay(y->c[1],null);
}
void maintain(splaynode *x, int o){
splaynode *p1=getneighbor(x,o),*p2;
int flag=0;
for(;;){
p2=getneighbor(p1,o);
int fp1=ok(p1),fp2=ok(p2);
if(fp1&&fp2){
int fcross=(cross(p2,p1,x)>=0)^o;
if(fcross){
p1=p2;
}else break;
}else if(!o&&fp1&&!fp2){
if(p1->yy)
p1=p2;
else break;
}else{
break;
}
}
splay(x,null);
if(!ok(p1)){
root->c[o]=null;
}else{
splay(p1,root);
root->c[o]->c[!o]=null;
}
}
void maintain(splaynode *x){
splaynode *pre=getneighbor(x,0),*suc=getneighbor(x,1);
int fpre=ok(pre),fsuc=ok(suc);
if(fpre&&fsuc&&cross(pre,x,suc)>=0||fsuc&&suc->y>=x->y){
del(x);
}else{
maintain(x,0);
maintain(x,1);
}
}
void insert(double X, double Y){
splaynode *x=root;
for(;;){
if(x->x==X&&x->y==Y) return;
if(Xx&&!ok(x->c[0])||X>=x->x&&!ok(x->c[1])){
int o=X>=x->x;
x->c[o]=newsplaynode(X,Y,x);
splay(x->c[o],null);
maintain(root);
return;
}
if(Xx){
x=x->c[0];
}else{
x=x->c[1];
}
}
}
double ask(double A, double B){
double k=-A/B;
splaynode *x=root;
for(;;){
splaynode *pre=getneighbor(x,0),*suc=getneighbor(x,1);
double k1=oo,k2=-oo;
if(ok(pre)){
k1=slope(x->x,x->y,pre->x,pre->y);
}
if(ok(suc)){
k2=slope(x->x,x->y,suc->x,suc->y);
}
if(k1>=k&&k>=k2){
splay(x,null);
return calc(A,B,x->x,x->y);
}else if(k>k1){
x=x->c[0];
}else{
x=x->c[1];
}
}
}
} tree;
int main(){
freopen(“1.in”,”r”,stdin);
freopen(“1.out”,”w”,stdout);
int N;
scanf(“%d %lf\n”,&N,&F[0]);
for(int i=1;i<=N;++i){
scanf("%lf %lf %lf\n",&A[i],&B[i],&R[i]);
}
tree.init();
for(int i=1;i1) F[i]=max(F[i],tree.ask(A[i],B[i]));
Y[i]=F[i]/(R[i]*A[i]+B[i]);
X[i]=Y[i]*R[i];
tree.insert(X[i],Y[i]);
}
printf(“%.3lf\n”,F[N]);
return 0;
}
[/cc]

Categories: OI
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: