首页 > 代码库 > bzoj1038题解

bzoj1038题解

【题意分析】

  求一个下凸壳与一段折线的距离。

【解题思路】

  先把直线按斜率排序,求出下凸壳,然后枚举所有的顶点的x坐标求最短y坐标差。

【参考代码】

技术分享
  1 #include <algorithm>  2 #include <cstdio>  3 #define REP(i,low,high) for(register int i=(low);i<=(high);++i)  4 #define __function__(type) /*__attribute__((optimize("-O2"))) inline */type  5 #define __procedure__ /*__attribute__((optimize("-O2"))) inline */void  6 using namespace std;  7    8 //defs {  9 #include <cmath> 10 template<typename real> 11 inline __function__(bool) fequals( 12     const real&one,const real&another,const real&eps=1e-6 13 ) {return fabs(one-another)<eps;} 14 template<typename real> 15 inline __function__(bool) funequals( 16     const real&one,const real&another,const real&eps=1e-6 17 ) {return fabs(one-another)>=eps;} 18 //} defs 19   20 //geometry { 21 template<typename T=double> struct Point 22 { 23     T x,y; Point(const T&_x=0,const T&_y=0):x(_x),y(_y) {} 24     __function__(bool) operator==(const Point<T>&thr)const 25     { 26         return fequals(x,thr.x)&&fequals(y,thr.y); 27     } 28     __function__(bool) operator!=(const Point<T>&thr)const 29     { 30         return funequals(x,thr.x)||funequals(y,thr.y); 31     } 32     __function__(Point<T>) operator+(const Point<T>&thr)const 33     { 34         return Point<T>(x+thr.x,y+thr.y); 35     } 36     __function__(Point<T>) operator-(const Point<T>&thr)const 37     { 38         return Point<T>(x-thr.x,y-thr.y); 39     } 40     __function__(Point<T>) operator*(const T&lambda)const 41     { 42         return Point<T>(x*lambda,y*lambda); 43     } 44     __function__(Point<double>) operator/(const T&lambda)const 45     { 46         return Point<double>(double(x)/lambda,double(y)/lambda); 47     } 48     __function__(double) theta()const 49     { 50         return x>0?(y<0)*2*M_PI+atan(y/x):M_PI+atan(y/x); 51     } 52     __function__(double) theta_x()const{return x?atan(y/x):M_PI/2;} 53     __function__(double) theta_y()const{return y?atan(x/y):M_PI/2;} 54 }; 55 template<typename T> 56 inline __function__(T) dot_product(const Point<T>&A,const Point<T>&B) 57 { 58     return A.x*B.x+A.y*B.y; 59 } 60 template<typename T> 61 inline __function__(T) cross_product(const Point<T>&A,const Point<T>&B) 62 { 63     return A.x*B.y-A.y*B.x; 64 } 65 template<typename T> 66 inline __function__(double) Euclid_distance(const Point<T>&A,const Point<T>&B) 67 { 68     return sqrt(pow(A.x-B.x,2),pow(A.y-B.y,2)); 69 } 70 template<typename T> 71 inline __function__(T) Manhattan_distance(const Point<T>&A,const Point<T>&B) 72 { 73     return fabs(A.x-B.x)+fabs(A.y-B.y); 74 } 75 struct kbLine 76 { 77     //line:y=kx+b 78     double k,b; kbLine(const double&_k=0,const double&_b=0):k(_k),b(_b) {} 79     __function__(bool) operator==(const kbLine&thr)const 80     { 81         return fequals(k,thr.k)&&fequals(b,thr.b); 82     } 83     __function__(bool) operator!=(const kbLine&thr)const 84     { 85         return funequals(k,thr.k)||funequals(b,thr.b); 86     } 87     __function__(bool) operator<(const kbLine&thr)const{return k<thr.k;} 88     __function__(bool) operator>(const kbLine&thr)const{return k>thr.k;} 89     template<typename T> 90     __function__(bool) build_line(const Point<T>&A,const Point<T>&B) 91     { 92         return fequals(A.x,B.x)?0:(k=double(A.y-B.y)/(A.x-B.x),b=A.y-k*A.x,1); 93     } 94     __function__(double) theta_x()const{return atan(k);} 95     __function__(double) theta_y()const{return theta_x()-M_PI/2;} 96     __function__(double) get(const double&x)const{return k*x+b;} 97 }; 98 __function__(bool) parallel(const kbLine&A,const kbLine&B) 99 {100     return A!=B&&(fequals(A.k,B.k)||A.k!=A.k&&B.k!=B.k);101 }102 __function__(Point<double>*) cross(const kbLine&A,const kbLine&B)103 {104     if(A==B||parallel(A,B)) return NULL; double _x=double(B.b-A.b)/(A.k-B.k);105     Point<double>*ret=new Point<double>(_x,A.k*_x+A.b); return ret;106 }107 //} geometry108  109 static int n; double x[310],y[310]; int stack[310]; kbLine L[310];110  111 int main()112 {113     scanf("%d",&n); REP(i,1,n) scanf("%lf",x+i); REP(i,1,n) scanf("%lf",y+i);114     REP(i,1,n-1) L[i].build_line(Point<>(x[i],y[i]),Point<>(x[i+1],y[i+1]));115     sort(L+1,L+n); int top=stack[1]=1; REP(i,2,n-1)116     {117         for(;i<=n&&(L[i]==L[stack[top]]||parallel(L[i],L[stack[top]]));++i);118         for(;i<=n&&top>1;--top)119         {120             Point<>*last=cross(L[stack[top-1]],L[stack[top]]),121                    * now=cross(L[     i      ],L[stack[top]]);122             if(last->x<now->x) break; delete last; delete now;123         }124         stack[++top]=i;125     }126     double ans=1e10; int j=2;127     REP(i,1,n)128     {129         for(;L[stack[j]].get(x[i])>L[stack[j-1]].get(x[i]);++j);130         ans=min(ans,L[stack[--j]].get(x[i])-y[i]);131     }132     REP(i,2,top)133     {134         Point<>*now=cross(L[stack[i-1]],L[stack[i]]);135         j=upper_bound(x+1,x+n+1,now->x)-x; kbLine tmp;136         tmp.build_line(Point<>(x[j-1],y[j-1]),Point<>(x[j],y[j]));137         ans=min(ans,now->y-tmp.get(now->x)); delete now;138     }139     return printf("%.3lf\n",ans),0;140 }
View Code

 

bzoj1038题解