latex預處理

\( \newcommand{\ord}[1]{\mathcal{O}\left(#1\right)} \newcommand{\abs}[1]{\lvert #1 \rvert} \newcommand{\floor}[1]{\lfloor #1 \rfloor} \newcommand{\ceil}[1]{\lceil #1 \rceil} \newcommand{\opord}{\operatorname{\mathcal{O}}} \newcommand{\argmax}{\operatorname{arg\,max}} \newcommand{\str}[1]{\texttt{"#1"}} \)
顯示具有 geometry 標籤的文章。 顯示所有文章
顯示具有 geometry 標籤的文章。 顯示所有文章

2016年2月20日 星期六

[ IOICAMP2016 ] 動態曼哈頓最短距離

題目:
因為IOICAMP的judge是暫時性的，所以有人備份了題目
http://codingsimplifylife.blogspot.tw/2016/02/ioi-camp-judge-37_4.html

解法:
CDQ分治不會寫，所以就用老派的kd tree去解吧，這裡提供兩種寫法:
  • 第一種寫法是動態的將點進行插入，因為必須要做到動態的插入操作，而一般kd tree不能用旋轉的方式來平衡，所以利用替罪羊樹的概念來平衡。(3.10s)
  •  第二種寫法是把所有操作讀入，把所有要插入的點先建成一顆kd tree，接著倒著作回來，如果遇到插入操作就把點從kd tree裡刪除，但是刪除的速度很慢，所以是壓線過的。(7.16)
兩種寫法如果再kdt.clear()時不做delete操作只把root=0的話會加快約2秒的時間(3.02s跟3.73s)

第一種作法code:
  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
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
#include<stdio.h>
#include<limits.h>
//using namespace std;
#ifndef SUNMOON_DYNEMIC_KD_TREE
#define SUNMOON_DYNEMIC_KD_TREE
#include<algorithm>
#include<vector>
#include<queue>
#include<cmath>
template<typename T,size_t kd>//kd表示有幾個維度
class kd_tree{
    public:
        struct point{
            T d[kd];
            inline T dist(const point &x)const{
                T ret=0;
                for(size_t i=0;i<kd;++i)ret+=std::abs(d[i]-x.d[i]);
                return ret;
            }
            inline bool operator<(const point &b)const{
                return d[0]<b.d[0];
            }
        };
    private:
        struct node{
            node *l,*r;
            point pid;
            int s;
            node(const point &p):l(0),r(0),pid(p),s(1){}
            inline void up(){
                s=(l?l->s:0)+1+(r?r->s:0);
            }
        }*root;
        const double alpha,loga;
        const T INF;//記得要給INF，表示極大值
        std::vector<node*> A;
        int qM;
        std::priority_queue<std::pair<T,point > >pQ;
        struct __cmp{
            int sort_id;
            inline bool operator()(const node*x,const node*y)const{
                return x->pid.d[sort_id]<y->pid.d[sort_id];
            }
        }cmp;
        void clear(node *o){
            if(!o)return;
            clear(o->l);
            clear(o->r);
            delete o;
        }
        inline int size(node *o){
            return o?o->s:0;
        }
        node* build(int k,int l,int r){
            if(l>r)return 0;
            if(k==kd)k=0;
            int mid=(l+r)/2;
            cmp.sort_id=k;
            std::nth_element(A.begin()+l,A.begin()+mid,A.begin()+r+1,cmp);
            node *ret=A[mid];
            ret->l=build(k+1,l,mid-1);
            ret->r=build(k+1,mid+1,r);
            ret->up();
            return ret;
        }
        inline bool isbad(node*o){
            return size(o->l)>alpha*o->s||size(o->r)>alpha*o->s;
        }
        void flatten(node *u,typename std::vector<node*>::iterator &it){
            if(!u)return;
            flatten(u->l,it);
            *it=u;
            flatten(u->r,++it);
        }
        bool insert(node*&u,int k,const point &x,int dep){
            if(!u){
                u=new node(x);
                return dep<=0;
            }
            ++u->s;
            if(insert(x.d[k]<u->pid.d[k]?u->l:u->r,(k+1)%kd,x,dep-1)){
                if(!isbad(u))return 1;
                if((int)A.size()<u->s)A.resize(u->s);
                typename std::vector<node*>::iterator it=A.begin();
                flatten(u,it);
                u=build(k,0,u->s-1);
            }
            return 0;
        }
        inline int heuristic(const int h[])const{
            int ret=0;
            for(size_t i=0;i<kd;++i)ret+=h[i];
            return ret;
        }
        void nearest(node *u,int k,const point &x,T *h,T &mndist){
            if(u==0||heuristic(h)>=mndist)return;
            point now=u->pid;
            int dist=u->pid.dist(x),old=h[k];
            /*mndist=std::min(mndist,dist);*/
            if(dist<mndist){
                pQ.push(std::make_pair(dist,u->pid));
                if((int)pQ.size()==qM+1){
                    mndist=pQ.top().first,pQ.pop();
                }
            }
            if(x.d[k]<u->pid.d[k]){
                nearest(u->l,(k+1)%kd,x,h,mndist);
                h[k]=abs(x.d[k]-u->pid.d[k]);
                nearest(u->r,(k+1)%kd,x,h,mndist);
            }else{
                nearest(u->r,(k+1)%kd,x,h,mndist);
                h[k]=abs(x.d[k]-u->pid.d[k]);
                nearest(u->l,(k+1)%kd,x,h,mndist);
            }
            h[k]=old;
        }
        std::vector<point>in_range;
        void range(node *u,int k,const point&mi,const point&ma){
            if(!u)return;
            bool is=1;
            for(int i=0;i<kd;++i)
                if(u->pid.d[i]<mi.d[i]||ma.d[i]<u->pid.d[i]){
                    is=0;break;
                }
            if(is)in_range.push_back(u->pid);
            if(mi.d[k]<=u->pid.d[k])range(u->l,(k+1)%kd,mi,ma);
            if(mi.d[k]>=u->pid.d[k])range(u->r,(k+1)%kd,mi,ma);
        }
    public:
        kd_tree(const T &INF,double a=0.75):alpha(a),loga(log2(1.0/a)),INF(INF){}
        inline void clear(){
            clear(root),root=0;
        }
        inline void build(int n,const point *p){
            clear(root),A.resize(n);
            for(int i=0;i<n;++i)A[i]=new node(p[i]);
            root=build(0,0,n-1);
        }
        inline void insert(const point &x){
            insert(root,0,x,std::__lg(size(root))/loga);
        }
        inline T nearest(const point &x,int k){
            qM=k;
            T mndist=INF,h[kd]={};
            nearest(root,0,x,h,mndist);
            mndist=pQ.top().first;
            pQ=std::priority_queue<std::pair<T,point > >();
            return mndist;/*回傳離x第k近的點的距離*/
        }
        inline const std::vector<point> &range(const point&mi,const point&ma){
            in_range.clear();
            range(root,0,mi,ma);
            return in_range;/*回傳介於mi到ma之間的點vector*/
        }
        inline int size(){return root?root->s:0;}
};
#endif
kd_tree<int,2> kdt(INT_MAX);
int t,n,a;
kd_tree<int,2>::point x;
int main(){
    scanf("%d",&t);
    while(t--){
        kdt.clear();
        scanf("%d",&n);
        while(n--){
            scanf("%d%d%d",&a,&x.d[0],&x.d[1]);
            if(a)printf("%d\n",kdt.nearest(x,1));
            else kdt.insert(x);
        }
    }
    return 0;
}

第二種做法code:
  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
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
#include<stdio.h>
#include<limits.h>
#include<assert.h>
//using namespace std; 
#ifndef SUNMOON_DYNEMIC_KD_TREE
#define SUNMOON_DYNEMIC_KD_TREE
#include<algorithm>
#include<vector>
template<typename T,size_t kd>
class kd_tree{
    public:
        struct point{
            T d[kd];
            inline T dist(const point &x)const{
                T ret=0;
                for(size_t i=0;i<kd;++i)ret+=std::abs(d[i]-x.d[i]);
                return ret;
            }
            inline bool operator<(const point &b)const{
                return d[0]<b.d[0];
            }
        };
    private:
        struct node{
            node *l,*r;
            point pid;
            node(const point &p):l(0),r(0),pid(p){}
        }*root;
        const T INF;
        std::vector<node*> A;
        int s;
        struct __cmp{
            int sort_id;
            inline bool operator()(const node*x,const node*y)const{
                return x->pid.d[sort_id]<y->pid.d[sort_id];
            }
        }cmp;
        void clear(node *o){
            if(!o)return;
            clear(o->l);
            clear(o->r);
            delete o;
        }
        node* build(int k,int l,int r){
            if(l>r)return 0;
            if(k==kd)k=0;
            int mid=(l+r)/2;
            cmp.sort_id=k;
            std::nth_element(A.begin()+l,A.begin()+mid,A.begin()+r+1,cmp);
            node *ret=A[mid];
            ret->l=build(k+1,l,mid-1);
            ret->r=build(k+1,mid+1,r);
            return ret;
        }
        inline int heuristic(const int h[])const{
            int ret=0;
            for(size_t i=0;i<kd;++i)ret+=h[i];
            return ret;
        }
        node **mnp;
        int mnk;
        void findmin(node*&o,int d,int k){
            if(!o)return;
            if(!mnp||o->pid.d[d]<(*mnp)->pid.d[d]){
                mnp=&o;
                mnk=k;
            }
            findmin(o->l,d,(k+1)%kd);
            if(d==k)return;
            findmin(o->r,d,(k+1)%kd);
        }
        void nearest_for_erase(node *&u,int k,const point &x,T *h,T &mndist){
            if(u==0||heuristic(h)>=mndist)return;
            point now=u->pid;
            int dist=u->pid.dist(x),old=h[k];
            if(dist<mndist){
                mnp=&u;
                mnk=k;
                if(!(mndist=dist))return;
            }
            if(x.d[k]<u->pid.d[k]){
                nearest_for_erase(u->l,(k+1)%kd,x,h,mndist);
                h[k]=abs(x.d[k]-u->pid.d[k]);
                nearest_for_erase(u->r,(k+1)%kd,x,h,mndist);
            }else{
                nearest_for_erase(u->r,(k+1)%kd,x,h,mndist);
                h[k]=abs(x.d[k]-u->pid.d[k]);
                nearest_for_erase(u->l,(k+1)%kd,x,h,mndist);
            }
            h[k]=old;
        }
    public:
        kd_tree(const T &INF):INF(INF),s(0){}
        inline void clear(){
            clear(root),root=0;
        }
        inline void build(int n,const point *p){
            clear(root),A.resize(s=n);
            for(int i=0;i<n;++i)A[i]=new node(p[i]);
            root=build(0,0,n-1);
        }
        inline bool erase(point p){
            T mndist=1,h[kd]={};
            nearest_for_erase(root,0,p,h,mndist);
            if(mndist)return 0;
            for(node **o=mnp;;){
                if((*o)->r);
                else if((*o)->l){
                    (*o)->r=(*o)->l;
                    (*o)->l=0;
                }else{
                    delete *o;
                    (*o)=0;
                    --s;
                    return 1;
                }
                mnp=0;
                findmin((*o)->r,mnk,(mnk+1)%kd);
                (*o)->pid=(*mnp)->pid;
                o=mnp;
            }
        }
        inline T nearest(const point &x){
            T mndist=INF,h[kd]={};
            nearest_for_erase(root,0,x,h,mndist);
            return mndist;/*回傳離x最近的點的距離*/
        }
        inline int size(){return s;}
};
#endif
kd_tree<int,2> kdt(INT_MAX);
int t,n;
kd_tree<int,2>::point x[200005],in[200005];
int ans[200005],a[200005],top;
int main(){
    scanf("%d",&t);
    while(t--){
        kdt.clear();
        scanf("%d",&n);
        top=0;
        for(int i=0;i<n;++i){
            scanf("%d%d%d",&a[i],&x[i].d[0],&x[i].d[1]);
            if(!a[i])in[top++]=x[i];
        }
        kdt.build(top,in);
        top=0;
        while(n--){
            if(a[n])ans[top++]=kdt.nearest(x[n]);
            else assert(kdt.erase(x[n]));
        }
        while(top--)printf("%d\n",ans[top]);
    }
    return 0;
}

張貼者： 於 沒有留言:
標籤： , ,

2015年12月30日 星期三

[ UVA ] 1298 - Triathlon

題目:
https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4044

解法:
假設比賽總長度為1，其中游泳長度x，自行車長度y，賽跑長度1-x-y，則選手i打敗選手j的條件是：
x/v[i] + y/u[i] + (1-xy)/w[i] < x/v[j] + y/u[j] + (1-xy)/w[j]
整理上式得到不等式：
(1/v[j]-1/w[j]-1/v[i]+1/w[i])x + (1/u[j]-1/w[j]-1/u[i]+1/w[i])y + 1/w[j]-1/w[i] > 0

對於每個選手i，都可以得到相對於選手j的如上不等式（不等式在二維坐標係是一個半平面），問題轉化為解n-1個格式為Ax+By+c>0的不等式，即求半平面交，如果半平面交非空，則輸出Yes
因為數字很小且題目要求精度，所以把A、B、C都乘上10000
最後記得加入x>0、y>0、1-x-y>0這三個半平面

code:
  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
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
#include<bits/stdc++.h>
using namespace std;
template<typename T>
struct point{
    T x,y;
    point(){}
    point(const T&dx,const T&dy):x(dx),y(dy){}
    inline const point operator+(const point &b)const{
        return point(x+b.x,y+b.y);
    }
    inline const point operator-(const point &b)const{
        return point(x-b.x,y-b.y);
    }
    inline const point operator*(const T &b)const{
        return point(x*b,y*b);
    }
    inline const point operator/(const T &b)const{
        return point(x/b,y/b);
    }
    inline const T dot(const point &b)const{
        return x*b.x+y*b.y;
    }
    inline const T cross(const point &b)const{
        return x*b.y-y*b.x;
    }
    inline point normal()const{/*求法向量*/
        return point(-y,x);
    }
    inline const T abs2()const{/*向量長度的平方*/
        return dot(*this);
    }
};
template<typename T>
struct line{
    line(){}
    point<T> p1,p2;
    line(const point<T>&x,const point<T>&y):p1(x),p2(y){}
    inline bool parallel(const line &l)const{/*直線平行*/
        return (p1-p2).cross(l.p1-l.p2)==0;
    }
    inline T cross(const point<T> &p)const{/*點和有向直線的關係，>0左邊、=0在線上<0右邊*/
        return (p2-p1).cross(p-p1);
    }
    inline point<T> line_intersection(const line &l)const{/*直線交點*/
        point<T> a=p2-p1,b=l.p2-l.p1,s=l.p1-p1;
        return p1+a*s.cross(b)/a.cross(b);
    }
};
template<typename T>
struct polygon{
    polygon(){}
    std::vector<point<T> > p;
    inline const point<T>& operator[](int id)const{
        return p[id];
    }
    inline static char sign(const T&x){
        return x>=0?1:-1;
    }
    inline static bool angle_cmp(const line<T>& A,const line<T>& B){
        point<T>a=A.p2-A.p1,b=B.p2-B.p1;
        char ay=sign(a.y),by=sign(b.y),ax=sign(a.x),bx=sign(b.x);
        return ay>by||(ay==by&&(ax*ay>bx*by||(ax*ay==bx*by&&a.cross(b)>0)));
    }
    inline int halfplane_intersection(std::vector<line<T> > &s){
        sort(s.begin(),s.end(),angle_cmp);
        int L,R,n=s.size();
        std::vector<point<T> > px(n);
        std::vector<line<T> > q(n);
        q[L=R=0]=s[0];
        for(int i=1;i<n;++i){
            while(L<R&&s[i].cross(px[R-1])<=0)--R;
            while(L<R&&s[i].cross(px[L])<=0)++L;
            q[++R]=s[i];
            if(q[R].parallel(q[R-1])){
                --R;
                if(q[R].cross(s[i].p1)>0)q[R]=s[i];
            }
            if(L<R)px[R-1]=q[R-1].line_intersection(q[R]);
        }
        while(L<R&&q[L].cross(px[R-1])<=0)--R;
        p.clear();
        if(R-L<=1)return 0;
        px[R]=q[R].line_intersection(q[L]);
        for(int i=L;i<=R;++i)p.push_back(px[i]);
        return R-L+1;
    }
};
const int maxn=105;
const double bw=10000;
polygon<double> poly;
vector<line<double> >s;
int n,v[maxn],u[maxn],w[maxn];
int main(){
    while(~scanf("%d",&n)&&n){
        for(int i=0;i<n;++i)scanf("%d%d%d",&v[i],&u[i],&w[i]);
        for(int i=0;i<n;++i){
            s.clear();
            bool ok=1;
            for(int j=0;j<n;++j)if(i!=j){
                if(v[i]<=v[j]&&u[i]<=u[j]&&w[i]<=w[j]){ok=0;break;}
                if(v[i]>=v[j]&&u[i]>=u[j]&&w[i]>=w[j])continue;
                double a=(bw/v[j]-bw/w[j])-(bw/v[i]-bw/w[i]);
                double b=(bw/u[j]-bw/w[j])-(bw/u[i]-bw/w[i]);
                double c=bw/w[j]-bw/w[i];
                point<double> t,x(b,-a);
                if(fabs(a)>fabs(b))t=point<double>(-c/a,0);
                else t=point<double>(0,-c/b);
                s.push_back(line<double>(t,t+x));
            }
            if(ok){
                s.push_back(line<double>(point<double>(0,0),point<double>(0,-1)));
                s.push_back(line<double>(point<double>(0,0),point<double>(1,0)));
                s.push_back(line<double>(point<double>(0,1),point<double>(-1,2)));
                if(!poly.halfplane_intersection(s))ok=0;
            }
            puts(ok?"Yes":"No");
        }
    }
    return 0;
}

張貼者： 於 沒有留言:
標籤： , , , ,
訂閱： 文章 (Atom)