首页 > 代码库 > 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 }
bzoj1038题解
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。