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"}} \)

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;
}

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

2015年12月28日 星期一

[ UVA ] 1396 - Most Distant Point from the Sea

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

解法:
這題要算距離圖多邊形邊最遠的點，想法是半平面交+二分搜尋，每次把多邊形的每條邊向內移動m單位，之後判斷半平面交面積是否為0，搜尋m的邊界

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
#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;
    }
};
int n;
vector<line<double> > l;
point<double> p[200],v[200],v2[200];
polygon<double> poly;
int main(){
    while(scanf("%d",&n)&&n){
        for(int i=0;i<n;++i)
            scanf("%lf%lf",&p[i].x,&p[i].y);
        for(int i=0;i<n;++i){
            v[i]=p[(i+1)%n]-p[i];
            v2[i]=v[i].normal()/sqrt(v[i].abs2());
        }
        l.resize(n);
        double L=0,R=10000;//二分搜
        while(R-L>1e-8){
            double mid=L+(R-L)/2;
            for(int i=0;i<n;++i)
                l[i]=line<double>(p[i]+v2[i]*mid,p[i]+v2[i]*mid+v[i]);
            int m=poly.halfplane_intersection(l);
            if(!m)R=mid;
            else L=mid;
        }
        printf("%.6lf\n",L);
    }
    return 0;
}

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

2015年12月25日 星期五

[ UVA ] 11168 - Airport

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

解法:
這題要用解析幾何的方式算點到直線距離。
先求凸包，可以知道最佳直線一定在凸包的邊上，由於所有點在直線的同一側，那麽對於所有點，他們的(Ax0+By0+C)符號相同，根據公式知直線一般式為Ax+By+C=0；點(x0,y0)到直線的距離為:
  • fabs(Ax0+By0+C)/sqrt(A*A+B*B)
所以只要先求​​出x的和以及y的和，能在O(1)計算所有距離和。

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
#include<bits/stdc++.h>
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 T cross(const point &b)const{
        return x*b.y-y*b.x;
    }
};
template<typename T>
struct line{
    line(){}
    point<T> p1,p2;
    T a,b,c;/*ax+by+c=0*/
    line(const point<T>&x,const point<T>&y):p1(x),p2(y){}
    inline void pton(){/*轉成一般式*/
        a=p1.y-p2.y;
        b=p2.x-p1.x;
        c=-a*p1.x-b*p1.y;
    }
};
template<typename T>
struct polygon{
    polygon(){}
    std::vector<point<T> > p;
    inline const point<T>& operator[](int id)const{
        return p[id];
    }
    inline static bool graham_cmp(const point<T>& a,const point<T>& b){
        return (a.x<b.x)||(a.x==b.x&&a.y<b.y);/*凸包排序函數*/
    }
    inline void graham(std::vector<point<T> > &s){/*凸包*/
        sort(s.begin(),s.end(),graham_cmp);
        p.resize(s.size()+1);
        int m=0;
        for(int i=0;i<(int)s.size();++i){
            while(m>=2&&(p[m-1]-p[m-2]).cross(s[i]-p[m-2])<=0)--m;
            p[m++]=s[i];
        }
        for(int i=s.size()-2,t=m+1;i>=0;--i){
            while(m>=t&&(p[m-1]-p[m-2]).cross(s[i]-p[m-2])<=0)--m;
            p[m++]=s[i];
        }
        if(s.size()>1)--m;
        p.resize(m);
    }
};
int t,n;
std::vector<point<double > >px;
polygon<double>p;
int main(){
    scanf("%d",&t);
    for(int cnt=1;cnt<=t;++cnt){
        scanf("%d",&n);
        px.resize(n);
        double ax=0,ay=0;
        for(int i=0;i<n;++i){
            scanf("%lf%lf",&px[i].x,&px[i].y);
            ax+=px[i].x;
            ay+=px[i].y;
        }
        p.graham(px);
        double ans=1e9;
        for(int i=p.p.size()-1,j=0;j<(int)p.p.size();i=j++){
            line<double>l(p[i],p[j]);
            l.pton();
            ans=std::min(ans,fabs(l.a*ax+l.b*ay+l.c*n)/sqrt(l.a*l.a+l.b*l.b));
        }
        printf("Case #%d: %.3f\n",cnt,p.p.size()>1?ans/n:0.0);
    }
    return 0;
}

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

2015年12月2日 星期三

[ zerojudge ] b487:變態史考古錯誤報導篇 (link cut tree)

題目:
http://zerojudge.tw/ShowProblem?problemid=b487
http://zerojudge.tw/ShowProblem?problemid=b486

解法:
本題的code也可以AC b486:變態史考古
link cut tree的基本操作加上維護子樹大小即可，注意的是本題不需要用到make_root的操作，每次的cut_parents()都會保證切下來的點是其子樹的根，所以將rev、down()、push_down()刪除可減少執行時間及記憶體。

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
#include<bits/stdc++.h>
using namespace std;
struct splay_tree{
    int ch[2],pa;
    int s;
    splay_tree():pa(0),s(0){ch[0]=ch[1]=0;}
}node[100005];
inline bool isroot(int x){
    return node[node[x].pa].ch[0]!=x&&node[node[x].pa].ch[1]!=x;
}
inline void up(int x){
    node[x].s=node[node[x].ch[0]].s+node[node[x].ch[1]].s+1;
}
inline void rotate(int x){
    int y=node[x].pa,z=node[y].pa,d=(node[y].ch[1]==x);
    node[x].pa=z;
    if(!isroot(y))node[z].ch[node[z].ch[1]==y]=x;
    node[y].ch[d]=node[x].ch[d^1];
    node[node[y].ch[d]].pa=y;
    node[y].pa=x,node[x].ch[d^1]=y;
    up(y);
    up(x);
}
inline void splay(int x){
    while(!isroot(x)){
        int y=node[x].pa;
        if(!isroot(y)){
            int z=node[y].pa;
            if((node[z].ch[0]==y)^(node[y].ch[0]==x))rotate(y);
            else rotate(x);
        }
        rotate(x);
    }
}
inline int access(int x){
    int last=0;
    while(x){
        splay(x);
        node[x].ch[1]=last;
        up(x);
        last=x;
        x=node[x].pa;
    }
    return last;
}
inline void cut_parents(int x){
    access(x);
    splay(x);
    node[node[x].ch[0]].pa=0;
    node[x].ch[0]=0;
}
inline void link(int x,int y){
    node[x].pa=y;
}
inline int find_root(int x){
    x=access(x);
    while(node[x].ch[0])x=node[x].ch[0];
    splay(x);
    return x;
}
inline int find_lca(int u,int v){
    access(u);
    return access(v);
}
int n,m,x,y;
int main(){
    while(~scanf("%d%d",&n,&m)){
        for(int i=1;i<=n;++i){
            node[i].pa=node[i].ch[0]=node[i].ch[1]=0;
            node[i].s=0;
        }
        for(char c[5];m--;){
            scanf("%s%d%d",c,&x,&y);
            if(c[0]=='n'){
                cut_parents(x);
                link(x,y);
            }else{
                if(find_root(x)!=find_root(y)){
                    puts("-1");
                    continue;
                }
                int u=node[access(find_lca(x,y))].s*2;
                int d=node[access(x)].s+node[access(y)].s;
                int g=__gcd(u,d);
                printf("%d/%d\n",u/g,d/g);
            }
        }
    }
    return 0;
}

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