題意：給出一個以n個點為輪廓的村莊，在村莊任意位置放一個瞭望塔，使瞭望塔能看到村莊的所有位置，求瞭望塔最低高度。
只我們發現只有這個點在每個直線所在半平面以上的時候才能看到，如樣例圖:
還注意到，只有在原圖的端點或半平面交的端點處才會更新答案。
#include<cstdio>#include<algorithm>#include<cstring>#include<cmath>using namespace std;const double esp=1e-8;const int maxn=310;int n,m;int dcmp(double x){ return x>esp?1:(x<-esp?-1:0); }struct Point{ double x,y; Point(){} Point(double X,double Y):x(X),y(Y){} bool Operator <(const Point& A)const{ return x<A.x; }};typedef Point Vector;Vector operator -(const Point& A,const Point& B){ return Vector(A.x-B.x,A.y-B.y); }Point operator +(const Point& A,const Vector& B){ return Vector(A.x+B.x,A.y+B.y); }Vector operator *(const Vector& A,const double& B){ return Vector(A.x*B,A.y*B); }double Cross(Vector A,Vector B){ return A.x*B.y-A.y*B.x; }struct Line{ Point P; Vector v; double ang; Line(){} Line(const Point& A,const Point& B){ v=B-A; P=A; ang=atan2(v.y,v.x); } bool operator <(const Line& A)const{ return ang<A.ang; }};bool Onleft(Line L,Point P){ return Cross(L.v,P-L.P)>0;}Point p[maxn],land[maxn];Line q[maxn],L[maxn];Point GetIntersection(Line a,Line b){ Vector u=a.P-b.P; double t=Cross(b.v,u)/Cross(a.v,b.v); return a.P+a.v*t;}void HalfPlaneIntersection(){ int l=1,r=1; sort(L+1,L+1+n); q[l]=L[1]; for(int i=2;i<=n;i++){ while(l<r && !Onleft(L[i],p[r-1])) r--; while(l<r && !Onleft(L[i],p[l])) l++; q[++r]=L[i]; if(l<r && !dcmp(Cross(q[r].v,q[r-1].v))){ r--; if(Onleft(q[r],L[i].P)) q[r]=L[i]; } if(l<r) p[r-1]=GetIntersection(q[r-1],q[r]); } while(l<r && !Onleft(q[l],p[r-1])) r--; p[r]=GetIntersection(q[r],q[l]); for(int i=l;i<=r;i++) q[i-l+1]=q[i]; m=r-l+1;}int x[maxn],y[maxn];int main(){ scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&x[i]); for(int i=1;i<=n;i++) scanf("%d",&y[i]),land[i]=Point(x[i],y[i]); for(int i=1;i<n;i++) L[i]=Line(land[i],land[i+1]); L[n]=(Line){Point(1e12,1e12),Point(-1e12,1e12)}; HalfPlaneIntersection(); sort(p+1,p+1+m); double ans=1e12; for(int i=1;i<=n;i++) for(int j=1;j<m;j++){ if(dcmp(x[i]-p[j].x)>=0 && dcmp(x[i]-p[j+1].x)<=0){ ans=min(ans,p[j].y+(p[j+1].y-p[j].y)/(p[j+1].x-p[j].x)*(x[i]-p[j].x)-y[i]); break; } } for(int j=1;j<=m;j++) for(int i=1;i<n;i++){ if(dcmp(p[j].x-x[i])>=0 && dcmp(p[j].x-x[i+1])<=0){ ans=min(ans,p[j].y-(1.0*y[i]+1.0*(y[i+1]-y[i])/(x[i+1]-x[i])*(p[j].x-x[i]))); break; } } ^_^新聞熱點
疑難解答
