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

張貼者： 於
標籤： , , , ,

沒有留言:

張貼留言

訂閱： 張貼留言 (Atom)