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

沒有留言:

張貼留言