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

張貼者： 於
標籤： , , ,

沒有留言:

張貼留言

訂閱： 張貼留言 (Atom)